埃拉托斯特尼筛法
找到一个素数,就把他的倍数给排除掉
欧拉筛法
在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。
#include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pii pair<int,int> #define int long long const int inf = 0x3f3f3f3f; const int maxn = 30001110; const int M = 1e9+7; int n,sum; bool prime[maxn]; int v[maxn],pos = 0; void eulor(int x) { for(int i = 2; i <= x; i++) { if(!prime[i]) v[++pos] = i,sum+=i; for(int j = 1; j <= pos; j++) { if(i*v[j] > x) break; prime[i*v[j]] = 1; sum += j; if(i%v[j] == 0) break; } } } void seive(int x) { for(int i = 2; i <= x; i++) { if(!prime[i]) //如果i是素数 { sum += i; for(int j = i*i; j <= x; j+=i) //就把i的倍数划掉 { if(!prime[j]) { prime[j] = 1; sum += i; } } } } } signed main() { cin>>n; //eulor(n); seive(n); cout<<sum<<endl; return 0; }
为什么的算法跑不过的算法???
第一个是eulor,第二个是埃氏。