文章目录
5.1 简单数学
PAT B1019/A1069
B1019
给定任一个各位数字不完全相同的 4 位正整数，如果我们先把 4 个数字按非递增排序，再按非递减排序，然后用第 1 个数字减第 2 个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的 6174，这个神奇的数字也叫 Kaprekar 常数。
例如，我们从6767开始，将得到
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
... ...
现给定任意 4 位正整数，请编写程序演示到达黑洞的过程。
输入格式：
输入给出一个 (0,104) 区间内的正整数 N。
输出格式：
如果 N 的 4 位数字全相等，则在一行内输出 N - N = 0000；否则将计算的每一步在一行内输出，直到 6174 作为差出现，输出格式见样例。注意每个数字按 4 位数格式输出。
输入样例 1：
6767
输出样例 1：
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
输入样例 2：
2222
输出样例 2：
2222 - 2222 = 0000
A1069
For any 4-digit integer except the ones with all the digits being the same, if we sort the digits in non-increasing order first, and then in non-decreasing order, a new number can be obtained by taking the second number from the first one. Repeat in this manner we will soon end up at the number 6174 – the black hole of 4-digit numbers. This number is named Kaprekar Constant.
For example, start from 6767, we’ll get:
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
... ...
Given any 4-digit number, you are supposed to illustrate the way it gets into the black hole.
Input Specification:
Each input file contains one test case which gives a positive integer N in the range (0,104).
Output Specification:
If all the 4 digits of N are the same, print in one line the equation N - N = 0000. Else print each step of calculation in a line until 6174 comes out as the difference. All the numbers must be printed as 4-digit numbers.
Sample Input 1:
6767
Sample Output 1:
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
Sample Input 2:
2222
Sample Output 2:
2222 - 2222 = 0000
#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(int a, int b) {
return a > b;
}
void to_arr(int n, int num[]) {//得到的结果是n对应数组的逆序
for (int i = 0; i < 4; i++) {
num[i] = n % 10;
n /= 10;
}
}
int to_num(int num[]) {
int sum = 0;
for (int i = 0; i < 4; i++) {
sum = sum * 10 + num[i];
}
return sum;
}
int main() {
int n, max, min;
scanf("%d", &n);
int num[5];
while (1) {
to_arr(n, num);
sort(num, num + 4);
min = to_num(num);
sort(num, num + 4, cmp);
max = to_num(num);
n = max - min;
printf("%04d - %04d = %04d\n", max, min, n);
if (n == 0 || n == 6174)
break;
}
return 0;
}
5.2 最大公约最小公倍数
codeup 1818
输入两个正整数,求其最大公约数和最小公倍数
输入格式：
每组输入两个正整数
输出格式：
输出其最大公约数和最小公倍数
输入样例：
49 14
输出样例：
7 98
//自己版本
#include<stdio.h>
int greatest_common_divisor(int n, int m) {
int min = m;
if (m > n)
min = n;
for (int i = min; i > 0; i--) {
if (n % i == 0 && m % i == 0)
return i;
}
}
int lowest_common_multiple(int n, int m) {
int max = n;
if (m > n)
max = m;
for (int i = max;; i++) {//死循环
if (i % n == 0 && i % m == 0)
return i;
}
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
int greatest = greatest_common_divisor(n, m);
int lowest = lowest_common_multiple(n, m);
printf("%d %d", greatest, lowest);
}
//算法笔记
#include<cstdio>
//求最大公约数的递归写法
int gcd(int a, int b) {
if (b == 0)return a;
else return gcd(b, a % b);
}
int main() {
int m, n;
while (scanf("%d%d", &m, &n) != EOF) {
printf("%d\n", gcd(m, n));
}
return 0;
}
5.3 素数
5.3.1 判断素数
遍历的时候从1到sqrt(n)
//判断素数
#include<math.h>
bool isPrime(int n) {
if (n <= 1)
return false;
int sqr = (int)sqrt(1.0 * n);//先把n转浮点数,再转int
for (int i = 2; i < sqr; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
5.3.2 获取素数
素数筛法
时间复杂度O(nloglogn)
//100以内的素数
#include<stdio.h>
const int maxn = 101;
int prime[maxn], pNum = 0;
bool p[maxn] = { 0 };
void Find_Prime() {
for (int i = 2; i < maxn; i++) {
if (p[i] == false) {
prime[pNum++] = i;
for (int j = i + i; j < maxn; j += i) {
p[j] = true;
}
}
}
}
int main() {
Find_Prime();
for (int i = 0; i < pNum; i++) {
printf("%d ", prime[i]);
}
return 0;
}
PAT B1013
令 P**i 表示第 i 个素数。现任给两个正整数 M≤N≤104，请输出 P**M 到 P**N 的所有素数。
输入格式：
输入在一行中给出 M 和 N，其间以空格分隔。
输出格式：
输出从 P**M 到 P**N 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。
输入样例：
5 27
输出样例：
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103
#include<stdio.h>
const int maxn = 1000001;
int prime[maxn], pNum = 0;
bool p[maxn] = { 0 };
void Find_Prime(int n) {
for (int i = 2; i < maxn; i++) {
if (p[pNum] == false) {
prime[pNum] = i;
if (pNum >= n)
break;
for (int j = i + i; j < maxn; j += i) {
p[j] = true;
}
}
}
}
int main() {
int m, n, count = 0;
scanf("%d %d", &m, &n);
Find_Prime(n);
for (int i = m; i <= n; i++) {
printf("%d", prime[i - 1]);
count++;
if (count % 10 == 0 && i < n) {
printf(" ");
}
else {
printf("\n");
}
}
return 0;
}
5.4 质因子分解
5.4.1 PAT A1059
Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1k1×p2k2×⋯×pmk**m.
Input Specification:
Each input file contains one test case which gives a positive integer N in the range of long int.
Output Specification:
Factor N in the format N = p1^k1*p2^k2*…*p**m^k**m, where p**i’s are prime factors of N in increasing order, and the exponent k**i is the number of p**i – hence when there is only one p**i, k**i is 1 and must NOT be printed out.
Sample Input:
97532468
Sample Output:
97532468=2^2*11*17*101*1291
#include<stdio.h>
#include<math.h>
const int maxn = 100010;
bool is_prime(int n) {
if (n == 1)
return false;
int sqr = (int)sqrt(1.0 * n);
for (int i = 2; i <= sqr; i++) {
if (n % i == 0)
return false;
}
return true;
}
int prime[maxn], pNum = 0;
void Find_Prime() {
for (int i = 0; i < maxn; i++) {
if (is_prime(i) == true) {
prime[pNum++] = i;
}
}
}
struct factor {
int x, cnt;
}fac[10];
int main() {
Find_Prime();
int n, num = 0;
scanf("%d", &n);
if (n == 1)
printf("1=1");
else {
printf("%d=", n);
int sqr = (int)sqrt(1.0 * n);
for (int i = 0; i < pNum && prime[i] <= n; i++) {
if (n % prime[i] == 0) {
fac[num].x = prime[i];
fac[num].cnt = 0;
while (n % prime[i] == 0) {
fac[num].cnt++;
n /= prime[i];
}
num++;
}
if (n == 1)
break;
}
if (n != 1) {
fac[num].x = n;
fac[num++].cnt = 1;
}
for (int i = 0; i < num; i++) {
if (i > 0) {
printf("%d", fac[i].x);
}
printf("%d", fac[i].x);
if (fac[i].cnt > 1) {
printf("^%d", fac[i].cnt);
}
}
}
return 0;
}