埃拉托斯特尼筛法
找到一个素数,就把他的倍数给排除掉
欧拉筛法
在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。
#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,第二个是埃氏。

京公网安备 11010502036488号