筛素数
题目 筛质数
思路分析
如果要找一段区间里 质数的个数
首先最容易想到的办法就是 对每个数判断一下是不是素数 是的话 cnt++
还是那句话 填空题用 编程题别想
tle
#include<bits/stdc++.h>
using namespace std;
bool is_prime(int x){
if(x<2) return false;
for(int i=2;i<=x/i;i++)
if(x%i==0)
return false;
return true;
}
int main(){
int n;cin>>n;
int cnt=0;
for(int i=2;i<=n;i++)
if(is_prime(i))
cnt++;
cout<<cnt;
return 0;
}
然后这里解释三种筛法
首先朴素的就是
从2——n 把所有的倍数全都标记掉不是素数 （能是2的倍数 反过来不就是除1和它本身外还可以有个2*x 肯定不是素数）
若某个数没被标记成非素数 就把它记录下来
这样就可以在\(O(nlog_n)\)内筛选出n内所有的素数
怎么表示某数的所有倍数 用到乘法原理本质是加法 2+2+2 三个2相加等于2*3
那么就可以用累加的方式 表示每次乘多一个for(int j=i;j≤n;j+=i)
167ms
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int primes[N];
bool st[N];
int cnt=0;
int n;
void get_primes(){
for(int i=2;i<=n;i++){
if(!st[i])
primes[cnt++]=i;//把素数存起来
for(int j=i;j<=n;j+=i){//不管是合数还是质数，都用来筛掉后面它的倍数
st[j]=true;
}
}
}
int main(){
cin>>n;
get_primes();
cout<<cnt;
return 0;
}
其实只需要把素数的倍数筛掉即可
合数的倍数会重复做很多无用功 比如2的倍数全筛了 4的倍数又来全筛 发现都已经被筛过了
这叫做 埃氏筛法 \(O(nloglog_n)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int primes[N];
bool st[N];
int cnt=0;
int n;
void get_primes(){
for(int i=2;i<=n;i++){
if(!st[i]){ //可以用质数就把所有的合数都筛掉;
primes[cnt++]=i;
for(int j=i;j<=n;j+=i)
st[j]=true;
}
}
}
int main(){
cin>>n;
get_primes();
cout<<cnt;
return 0;
}
还有一种线性筛 但是我感觉前面已经够用了 听一下思路得了
意思是说 每个被筛的数 范围再次缩小 从所有数去筛倍数 变成所有质数去筛倍数 再变成 最小质因子去筛倍数
34ms
void get_primes(){
for(int i=2;i<=n;i++){
if(!st[i])
primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){//primes[j]<=n/i:变形一下得到——primes[j]*i<=n,把大于n的合数都筛了就没啥意义了
st[primes[j]*i]=true;//用最小质因子去筛合数
//1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子
//那么只可能是此时的primes[j]<i的最小质因子,所以primes[j]*i的最小质因子就是primes[j];
//2)当有i%primes[j]==0时,说明i的最小质因子是primes[j]
//因此primes[j]*i的最小质因子也就应该是prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，
//就不是用最小质因子去更新了,因为i有最小质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该
//退出循环，避免之后重复进行筛选。
if(i%primes[j]==0)
break;
}
}
}
//完整代码
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int primes[N];
bool st[N];
int cnt=0;
int n;
void get_primes(){
for(int i=2;i<=n;i++){
if(!st[i])
primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0)
break;
}
}
}
int main(){
cin>>n;
get_primes();
cout<<cnt;
return 0;
}
思路不难 但是很多细节要搞懂就比较麻烦
若n在10的6次方的话,线性筛和埃氏筛的时间效率差不多,若n在10的7次方的话,线性筛会比埃氏筛快了大概一倍.
后面再说吧 先把线性筛放了 掌握埃氏筛就行了
代码实现
💬 评论