欧拉筛法求素数和

解题思路:暴力耗时长显然不是最优算法，这里提供一种效率极高的算法——欧拉筛法。

注意事项:看代码

参考代码:

#include <iostream>

using namespace std;

#define MAX 10000000

int Prim[MAX]={0};

int f[MAX];

void Isprime(int m,int n)

{

    int k = 0;

    int sum = 0;

    Prim[0] = 1;//0和1都不是素数，一开始就排除

    Prim[1] = 1;

    for(int i = 2; i < MAX; i++)

    {

        if(!Prim[i])//判断是否为素数

        {

            f[k++] = i;储存素数

        }

            for(int j = 0; j <= k&&i * f[j]<MAX;j++)

            {

                Prim[i*f[j]] = 1;

                if((i%f[j]) == 0)//重点，如果i == 9；此时素数有2，3，5，7.9*2=18，Prim[18] = 1；9*3=27，Prim[27]=1

                break;//但是因为9%3==0，所以break。因为5*9可以用3*15表示，如果此时计算了，i=15时又会重复计算。所以如果i%f[j] == 0,直接跳出循环

            }

    }

    for(int i = m; i <= n; i++)

    {

        if(!Prim[i])

        sum += i;

    }

    cout << sum << endl;

}

int main()

{

     int m,n;

        cin >> m >> n;

    Isprime(m,n);

    return 0;

}