Licae

用户名：lutaixue

访问量：4671

签　名：

剑指offer

等　　级
排　　名	5085
经　　验	1591
参赛次数	0
文章发表	9
年　　龄	18
在职情况	学生
学　　校	河南师范大学
专　　业

　　自我简介：

对算法极其感兴趣，对人工智能尤其偏爱

TA的其他文章

欧几里得算法未完全
浏览：701

深搜（新手上路）
浏览：646

宽搜（新手轻虐）
浏览：630

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

素数你太美！！！！

　　作者: Licae　　　　发表时间：2019-06-15 11:54:37 浏览：582　|　评论：0　

# 素数

素数的定义：在大于1的自然数中，除了1和它本身以外不再有其他因数。

## 解决的题目

原题链接1：[筛选N以内的素数](<https://www.dotcpp.com/oj/problem1022.html>)

原题链接2：[自定义函数处理素数](<https://www.dotcpp.com/oj/problem1029.html>)

原题链接3：[用筛选法求N内的素数](<https://www.dotcpp.com/oj/problem1084.html>)

原题链接4：[求素数问题](<https://www.dotcpp.com/oj/problem1139.html>)

原题链接5：[素数问题](<https://www.dotcpp.com/oj/problem1143.html>)

原题链接6：[素数回文](<https://www.dotcpp.com/oj/problem1250.html>)

原题链接7：[送分题素数](<https://www.dotcpp.com/oj/problem1259.html>)

原题链接8：[[蓝桥杯]\[算法提高VIP]找素数](<https://www.dotcpp.com/oj/problem1525.html>)

原题链接9：[[蓝桥杯]\[算法提高VIP]素数求和](<https://www.dotcpp.com/oj/problem1554.html>)

# 题解

针对上述题目会统一介绍筛选素数的方法，稍作改善便可以AC上述所有有题目

#### 新手版

```c
#include<stdio.h>
int main(){
	int i,j,n,flag;
	scanf("%d",&n);
	for(i = 2;i <= n;i++){
		flag = 1;
		for(j = 2;j < i;j++){
			if(i % j == 0)
				flag = 0;
		}
		if(flag)
			printf("%d\n",i);
	}
	return 0;
}
```

对于时间复杂度有要求的题目此方法不适合，建议参考下面方法

#### 进阶版(埃式筛法)

对于求1~n所有的素数，我们考虑的方法如下：如果找到一个数是素数，那么他的倍数一定不是素数，时间复杂度为O(nlog2n)

程序如下：（程序后面有配图共新手理解参考）

```c
#include<stdio.h>
#include<string.h>
int check[5000],primer[5000],n;
void isprimer(int n){
	memset(check,1,sizeof(check));
	check[1] = 0;
	int sum = 0,i,j;
	for(i = 2;i <= n;i++){
		if(check[i]) 
			for(j = 2;j * i <= n;j++){
				check[i * j] = 0;
			}	
	}
}
int main(){
	scanf("%d",&n);
	isprimer(n);
	for(int i = 2;i <= n;i++){
		if(check[i])
			printf("%d\n",i);
	}
	return 0;
}
```

![第一个图](https://i.loli.net/2019/06/15/5d046210d333220938.jpeg)

可以看出此方法有缺陷，有些数字筛选重复，下面介绍一种更优化的方法

### 高手版(欧拉筛选)

核心：每个合数必有一个最大因子（不包括它本身，用这个因子把合数筛掉。）还有另一种说法（每个合数必有一个最小素因子，用这个因子筛掉合数）

例如：

2：筛掉4 
3：筛掉6，9 
4：筛掉8 
5：筛掉10,15,25 
6：筛掉12 
7：筛掉14,21,35,49 
8：筛掉16 
9：筛掉18,27 
10：筛掉20 
11：筛掉22 
12: 筛掉24 
13: 筛掉26 
14: 筛掉28 
15: 筛掉30

代码如下：

```c
#include<stdio.h>
#include<string.h>
int check[5000],primer[5000],n;
void isprimer(int n){
	memset(check,1,sizeof(check));
	check[1] = 0;
	int sum = 0,i,j;
	for(i = 2;i <= n;i++){
		if(check[i])
			primer[sum++] = i;
		for(j = 0;j < sum;j++){
			if(i * primer[j] > n)
				break;
				check[i * primer[j]] = 0;
				if(i % primer[j] == 0)
					break;
		}
		
	}
}
int main(){
	scanf("%d",&n);
	isprimer(n);
	for(int i = 2;i <= n;i++){
		if(check[i])
			printf("%d\n",i);
	}
	return 0;
}
```

![第二个图片](https://i.loli.net/2019/06/15/5d0465bc9dfc620583.jpeg)

总结：筛选法是一个可以很大程度减少时间复杂度的方法，要好好学习，一但用到犹如画龙点睛，一跃AC。

第一次用markdown博客用的不太熟练，写作时间过长，以后要经常写，经常练习

有问题请提出，方便交流呀！！！！

0.0分

0 人评分

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

Licae

TA的其他文章

你可能喜欢

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

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

人民币问题（C语言代码）

去掉双斜杠注释（C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

素数你太美！！！！

评论区

精彩推荐

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

矩阵乘法（C++代码）

输出正反三角形（C语言代码）

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

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

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

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

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

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

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

Licae

TA的其他文章

你可能喜欢

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

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

人民币问题 （C语言代码）

去掉双斜杠注释 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

素数你太美！！！！

评论区

精彩推荐

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

矩阵乘法 （C++代码）

输出正反三角形 （C语言代码）

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

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

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

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

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

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

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

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

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

人民币问题（C语言代码）

去掉双斜杠注释（C语言代码）

　　评论区

矩阵乘法（C++代码）

输出正反三角形（C语言代码）