素数。。。素数。。。这这。。。
先来说说最low的吧，，算了，不说了。。看看代码吧
1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 const int maxn=1e3; 5 /*最low的*/ 6 int main(){ 7 int check[maxn]; 8 int prime[maxn]={0}; 9 int pos; 10 int flag; 11 for( int i=2; i<maxn; i++ ){ 12 flag=1; 13 for(int j=2; j<sqrt(i); j++ ){ 14 if(i%j==0){ 15 flag=0; 16 break; 17 } 18 } 19 if(flag==1) prime[pos++]=i; 20 } 21 for( int i=0; i<pos; i++ ){ 22 cout<<prime[i]<<" "; 23 } 24 cout<<endl; 25 return 0; 26 }
普通筛素数
-
思路
一次循环筛掉当前素数的倍数 -
缺点
- 存在重复筛选，比如6既可以被2筛掉，又可以被3筛掉。
- 原因：任意一个整数可以写成一些素数的乘积
n=p1^a * p2^b * p3^c(话说简书什么时候能上LaTeX啊)，其中p1<p2<p3，这样这个数n就能被p1,p2和p3筛掉
1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 const int maxn=1e6; 5 6 int main(){ 7 int check[maxn]={0}; 8 int prime[maxn]={0}; 9 int pos=0; 10 int flag; 11 for( int i=2; i<maxn; i++ ){ 12 if(!check[i]){//如果是素数 13 prime[pos++]=i; 14 } 15 for(int j=2*i; j<maxn; j+=i ){ 16 check[j]=1; 17 } 18 } 19 for( int i=0; i<pos; i++ ){ 20 cout<<prime[i]<<" "; 21 } 22 cout<<endl; 23 return 0; 24 }
线性筛素数
-
思路
当前数字是n=p1^a * p2^b * p3^c(p1<p2<p3且均为素数)，一次循环筛除小于等于p1的素数乘以n得到的数。比如p1之前有pi,pj和pk三个素数，则此次循环筛掉pi*n,pj*n,pk*n和p1*n，prime里的素数都是升序排列的，break时的prime[j]就是这里的p1。 -
优点：没有重复筛同一个数
- 原因：按照一个数的最小素因子筛选，比如6只按2筛去
1 #include<iostream> 2 using namespace std; 3 const int maxn=1e5; 4 5 int main(){ 6 int check[maxn]={0};//0代表时素数 7 int prime[maxn]={0}; 8 int pos=0; 9 int flag; 10 for( int i=2; i<maxn; i++ ){ 11 if(!check[i]){//如果是素数 12 prime[pos++]=i; 13 } 14 for( int j=0; j<pos&&i*prime[j]<maxn; j++ ){ 15 check[i*prime[j]]=1;//筛掉 16 if(i%prime[j]==0) break;/*避免重复筛选*/ 17 } 18 } 19 /*打印*/ 20 for( int i=0; i<pos; i++ ){ 21 cout<<prime[i]<<" "; 22 } 23 cout<<endl; 24 return 0; 25 }
线性筛选法其实挺不好理解的，我在这里才开始也是怎么想都想不通，后来把自己当成计算机一步一步的去演算，慢慢的也就明白了为什么他没有重复的去筛选同一个数。。。