7-1 素数求和(线性筛实现)

7-1 素数求和。

分数 10

中等

全屏浏览

切换布局

作者 魏英

单位 浙江科技大学

输入两个正整数m和n（1<=m<n<=500）统计并输出m和n之间的素数个数以及这些素数的和。

输入格式:

输入两个正整数m和n（1<=m<n<=500）。

输出格式:

输出m和n之间的素数个数以及这些素数的和。

输入样例:

在这里给出一组输入。例如：

1 10

输出样例:

在这里给出相应的输出。例如：

1和10之间有4个素数，这些素数的和是17。

题目解析：

大伙们在第一次看到这个题目的时候，我们首先要知道，什么是素数，所谓素数就是：

素数，又称质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。换句话说，素数只能被1和它自身整除。例如，2、3、5、7、11等都是素数，而4、6、8、9等则不是，因为它们可以被其他数整除

那么大伙肯定会想到有暴力算法的想法，那我就带大伙们想一想暴力求解的算法

暴力求解：

思想：暴力素数判断算法（即直接试除法）是最简单的素数判断方法，其核心思想是：对于给定的数 n，检查它是否能被 2 到 n​ 之间的所有整数整除。如果都不能整除，则 n 是素数；否则，n 是合数。

int sushu[N];      // 存储素数
int cnt = 0;       // 素数计数// 暴力判断是否为素数
bool isPrime(int n) {if (n <= 1) return false;for (int i = 2; i <= sqrt(n); i++) {//拿到一个数字，把他进行枚举，看这个数字有没有因子，如果有因子，那么这个数字就一定不是素数if (n % i == 0) return false;}return true;
}void panduan() {for (int i = 2; i <= 500; i++) {if (isPrime(i)) {sushu[cnt++] = i;}}
}

如果大伙们使用了素数的暴力算法，那么就缺失了对算法的意义，素数的暴力求解算法在时间复杂度会达到O（n²），在很多有关于素数求解的算法中，肯定是没有办法满足的，这时候我们就肯定要想到其他的办法去求解

线性筛：

这里给大家介绍一个求解素数非常快速的算法，首先，我们要知道，在数学的数字当中，一个数字他不是素数，就是合数，因此科学家就提出了线性筛这个算法，核心在于筛质数的时候规定一个数只能被它的最小质因数筛掉。

那么我们有了这个思想，我们就可以通过算法来解决这一个问题

①：开一个int类型数组，sushu[N]，来存储全部的sushu

②：开一个bool类型的数组，issushu[N]，来存储全部的数字，然后判断这个数字是否是素数，如果是，数组内容就是true，否则就是false

紧接着从

1. ​​内层循环 (j 遍历已知素数)​​ 对于每个 i，用已找到的素数 sushu[j] 去标记合数：

   • 合数为 sushu[j] * i。（素数的倍数一个不是素数）

2. ​​标记条件​​：sushu[j] <= 500 / i，即保证 sushu[j] * i ≤ 500，避免越界。

3.  ​​关键优化：if(i % sushu[j] == 0) break​​ 即当 i 能被 sushu[j] 整除时，立即终止内层循环。

4. ​​作用​​：确保每个合数只被它的最小素因子标记一次

例如：

• 当 i = 4，sushu[j] = 2 时，标记 4 * 2 = 8，然后 4 % 2 == 0，跳出循环。
• 避免后续用 sushu[j] = 3 标记 4 * 3 = 12（因为 12 会被 i = 6 时用 sushu[j] = 2 标记）

 这样就可以确保，不会被重复标记，增加效率

for(int i = 2; i <= 500; i++) {if(!issushu[i]) sushu[cnt++] = i;  // 如果i是素数，加入素数数组for(int j = 0; sushu[j] <= 500 / i; j++) {issushu[sushu[j] * i] = true;  // 标记合数if(i % sushu[j] == 0) break;   // 关键：保证每个合数只被标记一次}
}

然后我们现在知道，怎么把素数求出来之后，我们就只要把题目当中给的的n m范围，利用全局变量isshusu判断一下就可以

整体代码实现：

#include <bits/stdc++.h>
using namespace std;
#define N 501
int sushu[N];
bool issushu[N];
int cnt = 0;
void panduan(){issushu[1] = true;for(int i = 2;i<=500;i++){if(!issushu[i]) sushu[cnt++] = i;for(int j = 0;sushu[j]<=500/i;j++){issushu[sushu[j]*i] = true;if(i%sushu[j]==0) break;}}
}int main()
{panduan();
//		for(int i = 0;i<=10;i++)
//		 cout<<sushu[i];int m,n;cin>>m>>n;int cnt2 = 0;int ans = 0;for(int i = m;i<=n;i++){if(issushu[i] ==false)  {cnt2++;ans+=i;}}printf("%d和%d之间有%d个素数，这些素数的和是%d。" ,m,n,cnt2,ans);}

做题总结：

1. 时间复杂度为 ​​O(N)​​，比暴力算法高效
2. 每个合数仅被标记一次，无冗余操作。
3. 在理解的基础上，我们可以把这个算法模版背诵起来，在运用的时候就可以更加得心应手