埃拉托斯特尼筛法

埃拉托斯特尼筛法

埃拉托斯特尼筛法

思想：素数的倍数一定不是素数

要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

算法步骤：
给出要筛数值的范围n，找出n以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉，因为2的倍数一定是合数；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去。

如果觉得很难理解可以看下这个链接，是个动态的图片：
:Sieve_of_Eratosthenes_animation.gif

网易云公开课里面也有关于计算数论的视频，讲得蛮清晰的，强烈推荐：
.html

上题
pat有原题：

令Pi表示第i个素数。现任给两个正整数M <= N <= 10000，请输出PM到PN的所有素数。
输入在一行中给出M和N，其间以空格分隔。
输出从PM到PN的所有素数，每10个数字占1行，其间以空格分隔，但行末不得有多余空格。

输入
5 27

输出
11 13 17 19 23 29 31 37 41 43

47 53 59 61 67 71 73 79 83 89

97 101 103

分析
这题需要你输出第M个到第N个素数，如果一开始不知道这个埃拉托斯特尼筛法，那么就会像我一开始一样，将所有数字用是否是素数的函数进行判断。理解了埃拉托斯的思想后，题目要求的是10000个素数内，它的时间复杂度也就降到了(nlogn).

先上普通方法写的，在自己电脑上跑是没问题的，但是计算时间答不到题目要求的1s以内的时间。

//质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
#define maxsize 1000000
bool isPrime(int n)
{int m=2;while(n%m!=0 && m<n){m++;}if(m!=n)return false;elsereturn true;
}
int main()
{/* code */freopen(&#","r",stdin);int M,N;int k=0;//目前是第几个素数cin>>M>>N;if(M==1) {cout<<M<<" ";k++;}for(int i=2;i<=maxsize;i++){if(isPrime(i)){k++;if(k>N)return 0;if(M<=k&&k<=N){if(k==N)cout<<i;elsecout<<i<<" ";if(k==M+9 || (k-M-9)%10==0)cout<<endl;}}}return 0;
}

然后是用埃氏筛优化后的代码：

    #include <iostream>#include <stdio.h>#include <math.h>#define maxsize 1000000using namespace std;int main(){freopen(&#", "r", stdin);int a, b;cin >> a >> b;int k = 0;                       //记录第几个素数long long number[maxsize] = {0}; //未做标记即为0，表示是质数，不是合数for (int i = 2; i < maxsize; i++){if (number[i] == 0){int k = 2;for (int t = 2; t * i <= maxsize; t++){if (number[t * i] == 0)number[t * i] = 1; //做标记即为1，表示是合数}}}int temp = a;for (int y = 2; y < maxsize; y++){if (number[y] == 0){k++;if (k >= a && k <= b){if ((k - temp) % 9 == 0 && k != temp){cout << y << endl;temp += 10;}else if (k == b)cout << y;elsecout << y << " ";}}}}

除了注意需要将素数的倍数做标记，还要注意最后输出的格式，末尾不能有空格。