判断质数
- 计算 n 的算数平方根 k
- 判断 2..k 是否存在能被 n 整除的数
- 如果存在一个，return false
- 如果最后跳出了循环，说明不存在，return true
- 检验 2，3 这种特殊情况是否满足（对于2，3这种情况，k=1，不满足循环变量判定式，不会进入for内部的语句，直接 return true）
bool isPrime(int n) {
int k = (int) sqrt(n); // n 的算术平方根
for (int i = 2; i <= k; ++i) {
if (n % i == 0)
return false; // 能被整除的就不是质数
}
return true;
}
测试
int main() {
for (int i = 2; i < 30; ++i) {
cout << i << '\t' << isPrime(i) << endl;
}
return 0;
}
分解质因数
- 判断 n 是不是质数
- 如果是，直接输出 1×n
- 如果不是，循环判定，寻找 能被n整除且是质数的数
void factor(int n) {
if (isPrime(n))
cout << "1×" << n << endl;
else {
while (!isPrime(n)) {
int k = (int) sqrt(n);
int i;
for (i = 2; i <= k; i++) {
if (isPrime(i) && (n % i == 0)) // 能被n整除且是质数
break;
}
cout << i << "×";
n /= i;
}
cout << n << endl;
}
}
埃拉托色尼筛
- 与上面方法的唯一区别在于牺牲了空间
- 在每一轮循环中都需要一个griddle数组存储 [2,k] 之间的质因数
void factor(int n) {
if (isPrime(n))
cout << "1×" << n << endl;
else {
while (!isPrime(n)) {
int k = (int) sqrt(n);
int griddle[k - 1]; //最大筛长
int count = 0;
for (int i = 2; i <= k; i++) {
if (isPrime(i)) {
griddle[count] = i; //将筛出的质因数组成数组
count++;
}
}
int i;
for (i = 0; i < count; i++) { //count用来记录筛的长度
if (n % griddle[i] == 0) {
break;
}
}
cout << griddle[i] << "×";
n /= griddle[i];
}
cout << n << endl;
}
}
测试
int main() {
for (int i = 2; i < 30; ++i) {
cout << i << '\t';
factor(i);
}
return 0;
}
输出
2 1×2
3 1×3
4 2×2
5 1×5
6 2×3
7 1×7
8 2×2×2
9 3×3
10 2×5
11 1×11
12 2×2×3
13 1×13
14 2×7
15 3×5
16 2×2×2×2
17 1×17
18 2×3×3
19 1×19
20 2×2×5
21 3×7
22 2×11
23 1×23
24 2×2×2×3
25 5×5
26 2×13
27 3×3×3
28 2×2×7
29 1×29
