Atkin의 체가 매우 높은 한계에 대해 오작동합니다

Question

Project Euler problem 10을 해결하려고하는데 사용자가 2 백만 미만의 모든 소수의 합계를 계산해야합니다. 나는 pseudocode on Wikipedia을 연구하여 다음 사항을 서면으로 작성했습니다하지만 생성하는 대답은 잘못된 것 같다, 적어도 웹 사이트에 따르면 나는 그것을 입력하려고 할 때마다 :

int main() 
{ 
    int limit = 2000000; 
    int answer = 5; 

    std::vector<bool> isPrime; 
    for(int i = 0; i < limit; ++i){ 
     isPrime.push_back(false); 
    } 

    int n = 0; 
    for(int x = 1; x <= ceil(sqrt(limit)); ++x){ 
     for(int y = 1; y <= ceil(sqrt(limit)); ++y){ 

     n = 4*x*x + y*y; 
     if((n <= limit) && (n%12 == 1 || n%12 == 5)){ 
      isPrime.at(n) = ! isPrime.at(n); 
     } 

     n = 3*x*x + y*y; 
     if((n <= limit) && (n%12 == 7)){ 
      isPrime.at(n) = ! isPrime.at(n); 
     } 

     n = 3*x*x - y*y; 
     if((x > y) && (n <= limit) && (n%12 == 11)){ 
      isPrime.at(n) = ! isPrime.at(n); 
     } 
     } 
    } 

    for(n = 6; n <= ceil(sqrt(limit)); n += 2){ 
     if(isPrime.at(n)){ 
     for(int m = n*n; m < limit; m += n*n){ 
      isPrime.at(m) = false; 
     } 
     } 
    } 

    for(int i = 5; i < limit; i += 2){ 
     if(isPrime.at(i)){ 
     answer += i; 
     } 
    } 

    std::cout << "The sum of the primes below " << limit << " is " << answer << std::endl; 

    return 0; 
} 

다음 출력이 생성됩니다

The sum of all the primes below 2000000 is 1179908154 

필자는 수작업으로 검증 할 수있는 작은 한계를 테스트했으며이 수치는 실제로 올바르게 작동합니다. 나는 대답이 142913828922이되어야한다는 것을 나타내는 다른 사람들의 구현을 발견했지만, 나는 그들의 코드가 나의 것과 다른 곳을 알아낼 수 없다.

누구나 내가 뭘 잘못 볼 수 있습니까?

Answer 1

답변에 대해 부호가있는 32 비트 정수 만 있습니다. 실제 대답은 이고, 그 이상의 값인은 32 비트에 적합합니다. 따라서 64 비트 정수를 사용해야합니다. 대신 unsigned long long을 사용해보세요.

Answer 2

큰 수를 저장하기 위해 고유 한 클래스를 만들 수 있습니다. 또는 정수 배열을 사용하여 답변을 저장하고 각 숫자를 각 색인에 저장할 수 있습니다. (비록 부호없는 long long이 작동하지 않더라도) :)