Problem10 200万以下の全ての素数の和

問題

10以下の素数の和は2 + 3 + 5 + 7 = 17である.
200万以下の全ての素数の和を計算しなさい.

ソース(エラトステネスのふるいを使う方法)

#include <iostream>
#include <vector>

void main()
{
    //const int TargetVal = 10;
    const int TargetVal = 2000000;
    std::vector<int> IntVect;
    for (int I = 0; I <= TargetVal+1; I++){
        IntVect.push_back(I);
    }

    for (int I = 2; I <= TargetVal; I++) {
        if (IntVect.at(I) != 0) {
            for (int J = IntVect.at(I) * 2; J <= TargetVal; J += IntVect.at(I)) {
                IntVect.at(J) = 0;
            }
        }
    }

    __int64 sumVal = 0;
    for (int I = 2; I <= TargetVal; I++){
        sumVal += IntVect.at(I);
    }
    std::cout << sumVal << std::endl;
}

ソース(エラトステネスのふるいを使わない方法)

#include <iostream>

bool IsPrime(int pCheckNo);

void main()
{
    //const int TargetVal = 10;
    const int TargetVal = 2000000;

    __int64 SumVal = 0;
    for (int I = 2; I <= TargetVal; I++) {
        if (IsPrime(I)){
            SumVal +=I;
        }
    }

    std::cout << SumVal << std::endl;
}

bool IsPrime(int pCheckNo)
{
    for (int I=2;I*I <= pCheckNo;I++){
        if (pCheckNo%I==0) return false;
    }
    return true;
}

実行結果

142913828922

解説

エラトステネスのふるいを使ってもいいですね。