不会飞的章鱼

熟能生巧,勤能补拙;念念不忘,必有回响。

框架思维:将素数筛算法写成框架算法

任务

求 1 万以内所有素数的和。

编码

素数筛算法介绍

所谓素数筛,是将其产出的信息存储在一个标记数组中,数组的第 i 位,标记的是 i 这个数字是否是合数的信息。如果 i 这个数字是合数,数组下标为 i 的位置就被标记成为 1,如果 i 不是合数,则数组下标为 i 的位置就是 0。素数筛就是通过一套算法流程,产生一个这样的数组。

算法流程:

素数筛代码框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int prime[10005] = {0};
void init_prime() {
// 素数筛的标记过程
for (int i = 2; i * i <= 10000; i++) { //从 2 开始遍历到根号 10000,也就是 100。
//i <= sqrt(10000) == i * i <= 10000
//这种改变是有好处的,会在代码运行速度上做提升,毕竟开方运算是很慢的,远远没有单独做一个乘法操作要快。
if (prime[i]) continue; //判断 i 这个数字是否被标记过的,如果被标记过,就说明是合数,就不执行后续操作。
// 用 j 枚举所有素数 i 的倍数
for (int j = 2 * i; j <= 10000; j += i) {
prime[j] = 1; // 将 j 标记为合数
}
}
return ;
}

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#define MAX_N 10000
int prime[MAX_N + 5];

// 初始化素数表
void init_prime() {
prime[0] = prime[1] = 1;
for (int i = 2; i * i <= MAX_N; i++) {
if (prime[i]) continue;
for (int j = 2 * i; j <= MAX_N; j += i) {
prime[j] = 1; // 将 j 标记为合数
}
}
return ;
}

int main() {
init_prime();
int sum = 0;
for (int i = 2; i <= MAX_N; i++) {
sum += i * (1 - prime[i]); // 素数累加
}
printf("%d\n", sum);
return 0;
}

//输出:5736396

思考题

1,因子分解程序正确性证明

所谓的素因子分解,就是把一个整数,表示成为若干个素数相乘的形式,并且我们可以轻松的证明,这种只由素数表示的分解表示法,对于某个特定整数 N 来说,一定是唯一的。
例如,67689 这个数字就可以分解为:3 * 3 * 3 * 23 * 109 = 67689,其中 3、23、109 都是素数。

下面呢,有一段素因子分解的程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>

// 打印一个素因子,并且在中间输出 * 乘号
void print_num(int num, int *flag) {
if (*flag == 1) printf(" * ");
printf("%d", num);
*flag = 1;
return ;
}

int main() {
int n, i = 2, flag = 0, raw_n;
scanf("%d", &n);
raw_n = n;
// 循环终止条件,循环到 n 的平方根结束
while (i * i <= n) {
//①:只要 n 可以被 i 整除,就认为 i 是 n 的一个素因子
while (n % i == 0) {
print_num(i, &flag);
n /= i;
}
i += 1;
}
//②:如果最后 n 不等于 1,就说明 n 是最后一个素数
if (n != 1) print_num(n, &flag);
printf(" = %d\n", raw_n);
return 0;
}

试证明:

  • 1,第 18 行代码中,只要 n 可以被 i 整除,i 就一定是素数,为什么?
    假设 i 可以被 n 整除,但 i 不是素数,由算术基本定理可知,一个非素数的数字 N,一定可以分解为几个小于 N 的素数乘积的形式。我们不妨假设 i=p1​×p2​,这里 p1​ 和 p2​ 均为素数,如果变量 n 可以被 i 整除,那么 n 也一定可以被小于 i 的素数 p1​ 整除。而根据程序的运行流程,n 中已经不可能存在小于 i 的因子了,所以 p1​ 不具备存在的条件,故原假设不成立,i 是素数。

  • 2,第 25 行代码中,为什么只要 n 不等于 1,n 就一定是素数呢?
    在 while 循环处理过程中,数字 n 中已经不可能存在小于等于 i 的所有的因子了,又因为此时 i 是大于根号 n 的一个值,也就是说,在小于等于根号 n 范围内,找不到数字 n 的非 1 因子,而能够满足这种性质的数字,一定是素数。

小结

  • 想把具体“算法”升华成“算法思维”,首先要习惯性地总结算法的“框架思维”。
  • 素数筛是用素数去标记掉这个素数所有的倍数。
  • 清楚地知道素数筛在执行过程中,每一行的性质。
------ 本文结束------
如果本篇文章对你有帮助,可以给作者加个鸡腿~(*^__^*),感谢鼓励与支持!