C++ Atkin이 여러 컴포지트를 반환하는 경우

Question

C++에서 Atkin Sieve를 직접 구현 한 경우 약 860,000,000까지 소수를 생성합니다. 주변과 그 주변에서 프로그램은 몇 가지 합성물을 반환하기 시작합니다. 나는 발견 된 소수의 수를 세는 변수를 가지고 있고, ~ 860,000,000이 넘어야한다. 나는 Eratosthenes의 체와 비슷한 인터넷 프로그램에 대한 나의 수를 조사했다. 나는 프로그래밍에 익숙하지 않으므로 어리석은 실수 일 수있다.

어쨌든, 여기있다 : wikipedia 가입일

#include <iostream> 
#include <math.h> 
#include <time.h> 

int main(int argc, const char * argv[]) 
{ 
    long double limit; 
    unsigned long long int term,term2,x,y,multiple,count=2; 
    printf("Limit: "); 
    scanf("%Lf",&limit); 
    int root=sqrt(limit); 
    int *numbers=(int*)calloc(limit+1, sizeof(int)); 
    clock_t time; 


    //Starts Stopwatch 
    time=clock(); 


    for (x=1; x<root; x++) { 
     for (y=1; y<root; y++) { 
      term2=4*x*x+y*y; 
      if ((term2<=limit) && (term2%12==1 || term2%12==5)){ 
       numbers[term2]=!numbers[term2]; 
      } 
      term2=3*x*x+y*y; 
      if ((term2<=limit) && (term2%12==7)) { 
       numbers[term2]=!numbers[term2]; 
      } 
      term2=3*x*x-y*y; 
      if ((term2<=limit) && (x>y) && (term2%12==11)) { 
       numbers[term2]=!numbers[term2]; 
      } 

     } 
    } 


    //Print 2,3 
    printf("2 3 "); 



    //Sieves Non-Primes That Managed to Get Through 
    for (term=5; term<=root; term++) { 
     if (numbers[term]==true) { 
      multiple=1; 
      while (term*term*multiple<limit){ 
       numbers[term*term*multiple]=false; 
       multiple++; 
      } 
     } 
    } 

    time=clock()-time; 

    for (term=5; term<limit; term++) { 
     if (numbers[term]==true) { 
      printf("%llu ",term); 
      count++; 
     } 
    } 


    printf("\nFound %llu Primes Between 1 & %Lf in %lu Nanoseconds\n",count,limit,time); 



    return 0; 
} 

Answer 1

, (X, Y)에 대한

The following is pseudocode for a straightforward version of the algorithm: 
// arbitrary search limit 
limit ← 1000000   

// initialize the sieve 
for i in [5, limit]: is_prime(i) ← false 

// put in candidate primes: 
// integers which have an odd number of 
// representations by certain quadratic forms 
for (x, y) in [1, √limit] × [1, √limit]: 
    n ← 4x²+y² 
    if (n ≤ limit) and (n mod 12 = 1 or n mod 12 = 5): 
     is_prime(n) ← ¬is_prime(n) 
    n ← 3x²+y² 
    if (n ≤ limit) and (n mod 12 = 7): 
     is_prime(n) ← ¬is_prime(n) 
    n ← 3x²-y² 
    if (x > y) and (n ≤ limit) and (n mod 12 = 11): 
     is_prime(n) ← ¬is_prime(n) 

// eliminate composites by sieving 
for n in [5, √limit]: 
    if is_prime(n): 
     // n is prime, omit multiples of its square; this is 
     // sufficient because composites which managed to get 
     // on the list cannot be square-free 
     for k in {n², 2n², 3n², ..., limit}: 
      is_prime(k) ← false 

print 2, 3 
for n in [5, limit]: 
    if is_prime(n): print n 

[1 √limit] × [1 √limit]에서 : 너의 문제 야.

은 당신이 사용하고 있습니다 :

for (x=1; x<root; x++) 
     for (y=1; y<root; y++) 

가 대신 사용

for (x=1; x<=root; x++) 
     for (y=1; y<=root; y++) 

희망이 도움이!