数学学习
作者:
travel2.0
,
2024-01-29 09:06:44
,
所有人可见
,
阅读 45
筛质数
朴素筛法
算法分析:
1.对于每个数,筛去除其本身以外的倍数,即 *2 *3 ……;
2.用st[i] = 1,表示 i 个数被筛除;
#include<bits/stdc++.h>
using namespace std;
int n,cnt ;
const int N = 1e6+10;
int st[N];
void isprime(){
for(int i = 2;i <= n;i++){
if(!st[i]) {
cnt++;
}
for(int j = i + i;j <= n;j+=i){
st[j] = 1;
}
}
}
int main(){
cin>>n;
isprime();
cout<<cnt<<endl;
return 0;
}
埃氏筛法
算法分析:筛除每个质数的倍数;
#include<bits/stdc++.h>
using namespace std;
int n,cnt ;
const int N = 1e6+10;
int st[N];
void isprime(int n){
if(n < 2) return ;
for(int i = 2;i <= n;i++){
if(!st[i]){
cnt++;
for(int j = i + i;j <=n;j+=i){
st[j] = 1;
}
}
}
}
int main(){
cin>>n;
isprime(n);
cout<<cnt<<endl;
return 0;
}
线性筛法
算法分析:
1.用每个数的最小质因数来删除其本身,因为每个数的最小质因数是唯一的,所以每个数字都只会被删除一次;
故时间复杂度是O(n);速度是三种筛法中最快;
2.用prime[N] 存储质数,不是质数的st[i] = 0(不标记)
是质数的st[i] = 1(要标记)
3.其实可以看出当执行
`if(i % prime[j] == 0) break;` 时i必定为质数,
等价于 i == prime[j];
4.思路分析:
(1)因为prime[j]是从小到大枚举的,
1.对于 i % prime[j] != 0 则 prime[j] 不是 i 的最小质因数,
但它肯定是i * prime[j](这个时候要把i * prime[j] 看做1~n中等待筛选的数字,
这也也是一种方法可以解释为什么prime[j] <= n / i)
的最小质因数,而且i也是从小到大枚举的,所以每个数都有机会筛选到;
#include<bits/stdc++.h>
using namespace std;
int n,cnt ;
const int N = 1e6+10;
int st[N],prime[N];
void isprime(){
for(int i = 2;i <= n;i++){
if(!st[i]) prime[cnt++] = i;
for(int j = 0;prime[j] <= n / i;j++){
st[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
}
int main(){
cin>>n;
isprime();
cout<<cnt<<endl;
return 0;
}