流离之人追逐幻影

用户名：pwj666

访问量：60209

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

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

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

筛选N以内的素数（常规筛+埃氏筛+欧拉筛）（C++代码）

　　作者: 流离之人追逐幻影　　　　发表时间：2019-06-12 04:48:57 浏览：3786　|　评论：5　

原题链接：[编程入门]筛选N以内的素数

[判断素数算法【推荐点击】](https://blog.csdn.net/huang_miao_xin/article/details/51331710 "判断素数算法【推荐】")

```
在讲埃拉托斯特尼筛法的思路前前，先讲一下大家一般能够想到的思路。其实求素数个数的方法有很多种，萌新现在不宜追求过多种解法，一般会一两种就足够解决大部分素数的题目了。大佬就最追求完美筛吧。
```

**常规筛**
```
1.输入一个n,求1-n之间的素数，那么肯定要有一个循环将1到n都过一遍。
2.判定素数，除了1和它本身外没有其它的因数，所以，这里也要有一层循环，将2-n-1之间的数都判断一遍。
3.根据题目要求输出。
```

```
#include<iostream>
using namespace std;
int main(){
	int n,flag;
		cin>>n;
		for(int j=2;j<=n;j++){
			flag=1;//
			for(int i=2;i*i<=j;i++)
				if(j%i==0){
					flag=0;
					break;
				}
				if(flag==1)
					cout<<j<<endl;
		}
	return 0;
}
```
**优化点：**
```
1.首先要有一个标志位flag，事先标记为1，说明这个j是素数，在第二层循环中，只要有j可以被整除，那么就将其标记为0，退出第一层循环，紧解输出。
```
```
2.通常萌新们在第二层循环的条件部分写i<n,这样时间复杂度为O(n^2),不太好。
```
```
3.再优化一下，i<=j/2;聪明一点的萌新会发现，我只要判断到j的一半就行了，因为小于j一半的因数的个数和大于j一半的因数的个数是相等，也就是以j的一半为界成对出现。 这样时间复杂度就为O（n^2/2），好像还行，但阶数没有降下来。数据规模很大的话1/2就没有意义了。
```
```
4.再优化一下，i*i<=j;或者i<=sqrt(j) 其实已经有数学给出了证明，j的因数是以j的方根对半分布的，也就是说，小于j的方根的因数的个数和大于j方根的因数的个数是相等。这样时间复杂度就为O(nsqrt(n)) ,这样的话已经不错了，足够解决大部分的相关问题了。
```

------------
```
	   
补充：(一，首先脑子要有一个基本的模型解法或者基本思路，学习的话就根据前辈的思路走，不要直接看代码，先实操；二，建议从网上多阅读一些有关时间复杂度的资料，这样可以逐步建立代码优化的方向，空间复杂度和代码复杂度就略过了，不太重要。三，其实还有其它的优化方法来提高运行速度，优化思路增加约束（去除很明显不必或重复计算的）)
```

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

**埃氏筛**
```
基本思路：
首先，2是公认最小的质数，所以，先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数......

上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。

复杂度为O(nlogn)
```

```
#include<iostream>
using namespace std;
int main(){
    long long max=200000;
    long long  a[max],i,j;//可以计算到max
    long long n;
    cin>>n;
    a[0]=0;
    for(i=1;i<=n;i++)
        a[i]=i;//赋对应值 
        a[1]=0;
    for(i=2;i<=n;i++){
        if(a[i]==0)//被标记为零不是质数，
            continue;//跳过下面代码部分，直接进入下一次循环
        cout<<i<<endl;//筛出来的就是质数 输出
        for(j=i;i*j<=n&&j<n;++j)//就是上面写的基本思路
            a[i*j]=0;
    }
	return 0;
}
```

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

**欧拉筛**
```
线性筛，复杂度为O(n)。与埃氏筛相比，不会对已经被标记过的合数再进行重复标记，故效率更高。欧拉筛将合数分解为 (最小质因数 * 一个合数) 的形式，通过最小质因数来判断当前合数是否已经被标记过。
```
```
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10000;   // 表长
int prime[maxn], pNum = 0;    // prime记录素数，pNum记录素数个数
bool p[maxn] = {false};    // p记录当前数是否被筛去

void eulerSieve(int n) {// 查找记录2-n的素数{
    for (int i = 2; i <= n; i++){
        if (p[i] == false)  // 如果未被筛过，则为素数
            prime[pNum++] = i;

for (int j = 0; j < pNum; j++){

if (i * prime[j] > n) // 当要标记的合数超出范围时跳出
                break;

p[i * prime[j]] = true; // 将已经记录的素数的倍数进行标记
            if (i % prime[j] == 0)  //关键步骤
                break;
        }
    }
}
int main(){
    int n;
    int i;
    scanf("%d",&n);
    eulerSieve(n);
     for(i=0;i<pNum;i++)
        printf("%d\n",prime[i]);
    return 0;
}

```
```
欧拉筛的难点就在于对if (i % prime[j] == 0)这步的理解，当i是prime[j]的整数倍时，记 m = i / prime[j]，那么 i * prime[j+1] 就可以变为 (m * prime[j+1]) * prime[j]，这说明 i * prime[j+1] 是 prime[j] 的整数倍，不需要再进行标记(在之后会被 prime[j] * 某个数 标记)，对于 prime[j+2] 及之后的素数同理，直接跳出循环，这样就避免了重复标记。
```

赠人玫瑰，手有余香。点个赞吧。^-^

0.0分

90 人评分

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

　　评论区

aviyet

萌新一枚，最简单的方法为啥不给过啊：
#include <stdio.h>
int func(int n) {
	for (int i=2; i<n; i++) {
		if (n%i == 0) {
			return 0;
		}
	}
	return 1;
}
int main(void) {
	int n;
	scanf("%d", &n);
	for (int i=2; i<=n; i++) {
		if (func(i)) {
			printf("%d\n");
		}
	}
	return 0;
}

2020-04-12 18:15:53

卵不知道

欧拉筛没看懂。

2020-01-28 00:53:11

灰太狼

很棒，谢谢

2019-11-14 12:54:10

myaijarvis

没看懂，哈哈！

2019-08-03 18:10:21

ppp

学习到了--

2019-06-16 11:35:21

流离之人追逐幻影

TA的其他文章

你可能喜欢

母牛的故事（C语言代码）

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

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

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

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

筛选N以内的素数（常规筛+埃氏筛+欧拉筛）（C++代码）

评论区

精彩推荐

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

程序员的表白（C语言代码）

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

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

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

C语言考试练习题_一元二次方程（C语言代码）

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

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

1126题解

流离之人追逐幻影

TA的其他文章

你可能喜欢

母牛的故事 （C语言代码）

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

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

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

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

筛选N以内的素数（常规筛+埃氏筛+欧拉筛） （C++代码）

评论区

精彩推荐

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

程序员的表白 （C语言代码）

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

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

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

C语言考试练习题_一元二次方程 （C语言代码）

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

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

1126题解

母牛的故事（C语言代码）

筛选N以内的素数（常规筛+埃氏筛+欧拉筛）（C++代码）

　　评论区

程序员的表白（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）