埃拉托斯特尼筛法

找到一个素数,就把他的倍数给排除掉

欧拉筛法

在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。

#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,第二个是埃氏。
图片说明
图片说明