求质素（素数）
2020-11-04 本文已影响0人
优劣在于己
举个例子：求2020(可泛指n)内的所有质素(素数)，方法如下：
存在于个人总结，算法多种多样，看个人的思维想法吧
方法一：O(n^2)
最最最最最普通的了，就两个for循环，不想多说
int p[2020],cnt=0;
void Prime(){
for(int i=2;i<=2020;i++){
bool fl=true;
for(int j=2;j<i;j++)
if(i%j==0){
fl=false;
break;
}
if(fl)p[cnt++]=i;
}
}
想要更快一点，无非是将 j<i 改为 j<√i
方法二：O(nloglogn)埃拉特斯特尼筛法
从2到2020（2020可泛指n）开始，先筛去n内所有2的倍数，然后每次从下一个剩下的数（必然为质数）开始，筛去其n内所有的倍数，最后剩下的数都是质数。
设置p[]储存素数
vis[]为标记数组，即0为未标记的，1为标记的，也就是某个数的倍数
int p[2020],vis[2021],cnt=0;
void Prime(){
memset(vis,0,sizeof vis);
for(int i=2;i<=2020;i++){
if(!vis[i])p[cnt++]=i;
for(int j=i*i;j<2020;j+=i)
vis[j]=1;
}
}
方法三：O(n)欧拉线性筛法
在第二种方法里面，会发现有合数（ps：合数即为素数的倍数，如：18=2*9=3*6）被重复筛选过了，先上代码吧
int p[2020],vis[2021],cnt=0;
void Prime(){
memset(vis,0,sizeof vis);
for(int i=2;i<=2020;i++){
if(!vis[i])p[cnt++]=i;
//cout<<"i="<<i<<endl;
for(int j=0;j<cnt&&i*p[j]<=2020;j++){
//cout<<" j="<<j<<" prime["<<j<<"]="<<prime[j]<<" i*prime[j]="<<i*prime[j]<<endl;
v[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
}
来解释一下里面的一些代码意思吧
首先 i*p[j] 表示地是质素的倍数了，然后标记
最核心的也就是那个跳出语句 if(i%p[j]==0)break
为什么要跳出呢，看举例子吧（本弱弱喜欢举例子，比较好理解，哈哈哈哈）
i = 2
j = 1 prime[1] = 2 i*prime[j] = 4
i = 3
j = 1 prime[1] = 2 i*prime[j] = 6
j = 2 prime[2] = 3 i*prime[j] = 9
i = 4
j = 1 prime[1] = 2 i*prime[j] = 8
i = 5
j = 1 prime[1] = 2 i*prime[j] = 10
j = 2 prime[2] = 3 i*prime[j] = 15
j = 3 prime[3] = 5 i*prime[j] = 25
i = 6
j = 1 prime[1] = 2 i*prime[j] = 12
i = 7
j = 1 prime[1] = 2 i*prime[j] = 14
j = 2 prime[2] = 3 i*prime[j] = 21
j = 3 prime[3] = 5 i*prime[j] = 35
j = 4 prime[4] = 7 i*prime[j] = 49
i = 8
j = 1 prime[1] = 2 i*prime[j] = 16
i = 9
j = 1 prime[1] = 2 i*prime[j] = 18
j = 2 prime[2] = 3 i*prime[j] = 27
i = 10
j = 1 prime[1] = 2 i*prime[j] = 20
……
……
有没有看出点什么？，没有的话，我把它再单独拿出来
i = 2
j = 1 prime[1] = 2 i*prime[j] = 4
i = 4
j = 1 prime[1] = 2 i*prime[j] = 8
i = 8
j = 1 prime[1] = 2 i*prime[j] = 16
很明显了吧，就是当 i 恰好是 p[] 的倍数的时候，就会标记 i*p[],并且跳出
当 i*p[] 被标记时，下一次就会标记它的倍数的，自然就只被标记了一次
倘若不跳出，就会出现合数被多次标记的情况，如：
i = 2
j = 1 prime[1] = 2 i*prime[j] = 4
i = 3
j = 1 prime[1] = 2 i*prime[j] = 6
j = 2 prime[2] = 3 i*prime[j] = 9
i = 4
j = 1 prime[1] = 2 i*prime[j] = 8
j = 2 prime[2] = 3 i*prime[j] = 12
i = 5
j = 1 prime[1] = 2 i*prime[j] = 10
j = 2 prime[2] = 3 i*prime[j] = 15
j = 3 prime[3] = 5 i*prime[j] = 25
i = 6
j = 1 prime[1] = 2 i*prime[j] = 12
j = 2 prime[2] = 3 i*prime[j] = 18
j = 3 prime[3] = 5 i*prime[j] = 30
i = 7
j = 1 prime[1] = 2 i*prime[j] = 14
j = 2 prime[2] = 3 i*prime[j] = 21
j = 3 prime[3] = 5 i*prime[j] = 35
j = 4 prime[4] = 7 i*prime[j] = 49
i = 8
j = 1 prime[1] = 2 i*prime[j] = 16
j = 2 prime[2] = 3 i*prime[j] = 24
j = 3 prime[3] = 5 i*prime[j] = 40
j = 4 prime[4] = 7 i*prime[j] = 56
i = 9
j = 1 prime[1] = 2 i*prime[j] = 18
j = 2 prime[2] = 3 i*prime[j] = 27
j = 3 prime[3] = 5 i*prime[j] = 45
j = 4 prime[4] = 7 i*prime[j] = 63
再次提出来看吧
i = 4
j = 1 prime[1] = 2 i*prime[j] = 8
j = 2 prime[2] = 3 i*prime[j] = 12
i = 5
j = 1 prime[1] = 2 i*prime[j] = 10
j = 2 prime[2] = 3 i*prime[j] = 15
j = 3 prime[3] = 5 i*prime[j] = 25
i = 6
j = 1 prime[1] = 2 i*prime[j] = 12
j = 2 prime[2] = 3 i*prime[j] = 18
j = 3 prime[3] = 5 i*prime[j] = 30
