JakeLin

###### 1.以后遇到素数问题，二话不说用筛选法（提高效率）构造素数表
其中Prime[i]初始全为0，若置为1说明不是素数（反之亦可）
```cpp
int Prime[maxn]; 
void buildPrime(int n){
	for(int i=2;i<=sqrt(n);i++){   //这里为什么是sqrt（n）
		if(Prime[i]==0){
			for(int j=i*i;j<maxn;j+=i){  //这里为什么从i*i开始
				Prime[j]=1;
			}			
		}
	}
}
```
> 其中的两个为什么是属于筛选法的优化，你可以另外了解一下

------------

###### 2.根据题目要求查表
例如本题要求n之前（包括n）的素数和，只需遍历素数表，将n前是素数的累加即可
```cpp
int main(){
	int n;
	scanf("%d",&n);
	buildPrime(n);
	long long ans=0;
	for(int i=2;i<=n;i++){
		if(Prime[i]==0){
			ans+=i;
			//cout<<i<<endl;
		}
	}
	cout<<ans;
    return 0;
}
```
完整代码如下：
```cpp
#include<stdio.h>
#include<iostream>
using namespace std;
const int maxn = 2000010;
int Prime[maxn]; 
void buildPrime(int n){
	for(int i=2;i<=sqrt(n);i++){
		if(Prime[i]==0){
			for(int j=i*i;j<maxn;j+=i){
				Prime[j]=1;
			}			
		}
	}
}
int main(){
	int n;
	scanf("%d",&n);
	buildPrime(n);
	long long ans=0;
	for(int i=2;i<=n;i++){
		if(Prime[i]==0){
			ans+=i;
		}
	}
	cout<<ans;
    return 0;
}
```
> 素数问题八九不离十，这个模板可以解决大部分问题

0.0分

8 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JakeLin

TA的其他文章

你可能喜欢

C二级辅导-分段函数（C++代码）

C语言程序设计教程（第三版）课后习题6.10 （Java代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C二级辅导-计负均正（C语言代码）

简单的a+b （C语言代码）

素数求和（C/C++）素数问题通用解法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

校门外的树（C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

Cylinder （C语言描述，蓝桥杯）

Tom数（C语言代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）

The 3n + 1 problem （C语言代码）

Quadratic Equation （C语言代码）

JakeLin

TA的其他文章

你可能喜欢

C二级辅导-分段函数 （C++代码）

C语言程序设计教程（第三版）课后习题6.10 （Java代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C二级辅导-计负均正 （C语言代码）

简单的a+b （C语言代码）

素数求和 （C/C++）素数问题通用解法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

校门外的树 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

Cylinder （C语言描述，蓝桥杯）

Tom数 （C语言代码）

C语言训练-亲密数 （C语言描述,反正怎么都能对）

The 3n + 1 problem （C语言代码）

Quadratic Equation （C语言代码）

C二级辅导-分段函数（C++代码）

C二级辅导-计负均正（C语言代码）

素数求和（C/C++）素数问题通用解法

　　评论区

校门外的树（C语言代码）

Tom数（C语言代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）