宿雨

用户名：dotcpp0590198

访问量：150

签　名：

等　　级
排　　名	33668
经　　验	454
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

1084 用筛法求之N内的素数 C语言常规思路+素数表优化
浏览：122

你可能喜欢

1084 用筛法求之N内的素数 C语言常规思路+素数表优化

　　作者: 宿雨　　　　发表时间：2022-10-01 11:02:43 浏览：122　|　评论：0　

原题链接：用筛法求之N内的素数

###### 原题链接：[https://www.dotcpp.com/oj/problem1084.html][https://www.dotcpp.com/oj/problem1084.html]
[https://www.dotcpp.com/oj/problem1084.html]: https://www.dotcpp.com/oj/problem1084.html
# 常规思路
通过遍历，寻找 2 ~ n-1 是否有可以整除 n 的数，如果没有，则n为素数。
代码如下：
```c
    int main()
    {
    	int n,i,j;
    	scanf("%d",&n);
    	for(i=2;i<=n;i++)//素数从2开始算，0和1都不是素数。i为寻找到n为止的素数
    	{
    		for(j=2;j<i;j++)//j的功能为 “判断i是否是素数如果为素数，把其输出”
    			if(!(i%j))// !(i%j) 等价于 i%j==0 判断i是否能被整除。
    			{
    				j=0;//如果能整除，把j赋值为0，表示i不是素数,并且跳出内层for循环
    				break;
    			}
    		if(j>0)//j>0 表示i没有被j整除 i为素数
    		    printf("i: %d\n",i);
    	}
    	return 0;
    }
```
![](/image_editor_upload/20221001/20221001105935_92201.png)
  这样运算虽然简单，但是运算时间会大大增加，如果N值更大一些，需要时间会更久。
  
  我们何不换一个思路，与其计算每个数是否为素数，倒不如计算n是否能被比它小的素数整除，如果不能被整除，就是素数。并且把遇到的素数记录下来，存储起来。只需要计算是否能被素数整除，这样我们就得到了一个新的思路“筛除法”，也叫“筛法”。

# 筛法
具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。
代码如下：
```c
int main()
{
	int num[100]={2};//数组为我们记录的素数表
	int n,i,j,count=0;//count 为素数表的结尾地方，如果遇到新的素数，可以通过count存储进入数组
	scanf("%d",&n);
	for(i=2;i<=n;i++)
	{
		for(j=0;j<=count;j++)
			if(!(i%num[j]))//此步和常规思路一样，但我们只用判断素数能否整除i，num[j]为素数表里的素数
			{
				j=0;//如果整除，j=0 并且退出内循环
				break;
			}	
		if(j>0)//如果 j>0 表明i为素数 素数表做记录
		    num[++count]=i;//++count的意思是数组下标向后一格，将新的素数存入表中
	}
	for(j=0;j<=count;j++)//最后遍历数组，输出素数表
		printf("%d\n",num[j]);
	return 0;
}
```
![](/image_editor_upload/20221001/20221001105947_42036.png)
个人见解，如果有问题的地方，评论区请斧正

0.0分

1 人评分

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

宿雨

TA的其他文章

你可能喜欢

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

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

一个简单易懂的代码

你的开发任务（C++代码）写到一半，等有心情回来补全

【出圈】（C++代码）（典型的约瑟夫环——链表解决）

1084 用筛法求之N内的素数 C语言常规思路+素数表优化

评论区

精彩推荐

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

点我有惊喜！你懂得！

数组输出（C语言代码）

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

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

输出正反三角形（C语言代码）格式错误！！！

A+B for Input-Output Practice (IV) （C语言代码）

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

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

【矩阵】（C++代码）

宿雨

TA的其他文章

你可能喜欢

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

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

一个简单易懂的代码

你的开发任务 （C++代码）写到一半，等有心情回来补全

【出圈】 （C++代码）（典型的约瑟夫环——链表解决）

1084 用筛法求之N内的素数 C语言常规思路+素数表优化

评论区

精彩推荐

C二级辅导-同因查找 （C++代码）（42的倍数，，所以直接递加42输出）

点我有惊喜！你懂得！

数组输出 （C语言代码）

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

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

输出正反三角形 （C语言代码）格式错误！！！

A+B for Input-Output Practice (IV) （C语言代码）

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

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

【矩阵】 （C++代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

【出圈】（C++代码）（典型的约瑟夫环——链表解决）

　　评论区

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

数组输出（C语言代码）

输出正反三角形（C语言代码）格式错误！！！

【矩阵】（C++代码）