Atkin的C++篩選返回幾個複合物

Question

我已經使用C++自己實現了Atkin的Sieve，它生成的精品直到860,000,000左右。在那裏和更高的節目開始返回幾個複合材料，或者我認爲。我在程序內部有一個變量來計算髮現的素數，在〜8億6000萬的數量比它應該是更多。我檢查了我的計數與Eratosthenes Sieve的一個類似程序以及幾個互聯網資源。我是編程新手，所以這可能是一個愚蠢的錯誤。

無論如何，在這裏它是：

#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

從wikipedia，

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 

爲（X，Y）在[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++) 

希望這有助於！