Title: C++ Sieve of Atkin Returning Several Composites
Tags: c++;algorithm;primes;sieve-of-atkin
Question: I have made my own implementation of the Sieve of Atkin in C++, it generates primes fine until about 860,000,000. Around there and higher the program begins to return several composites, or so I think. I have a variable inside the program the counts the number of primes found, and at ~860,000,000 the count is more than it should be. I checked my count against a similar program for the Sieve of Eratosthenes, and several internet resources. I am new to programming so it is likely a stupid mistake.

Anyway, here it is:

```#include <iostream&gt;
#include <math.h&gt;
#include <time.h&gt;

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",&amp;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) &amp;&amp; (term2%12==1 || term2%12==5)){
                numbers[term2]=!numbers[term2];
            }
            term2=3*x*x+y*y;
            if ((term2<=limit) &amp;&amp; (term2%12==7)) {
                numbers[term2]=!numbers[term2];
            }
            term2=3*x*x-y*y;
            if ((term2<=limit) &amp;&amp; (x&gt;y) &amp;&amp; (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 &amp; %Lf in %lu Nanoseconds\n",count,limit,time);



    return 0;
}
```

Comment: Yes the maximum is limit, and if 4*x*x+y*y > limit then the value is useless because it is out of range of the limit.

Comment: I don't think it is either, but calloc (allocates memory) must use a pointer.

Comment: you could have `unsigned char *` too, no need for ints. but better, use `vector`. No manual `malloc` calls, and it is bit-packed.

Comment: what is maximum `limit`?

Comment: what if ` 4*x*x+y*y > limit  ` ?

Comment: Probably not related to the question, but why do you use int* numbers for storing bool values?

Here is the accepted answer: From  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 &gt; 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
```

for (x, y) in [1, √limit] × [1, √limit]: is your problem .  

You have used :

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

Instead use :  

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

Hope this helps ! 

Comment for this answer: Thanks! Works perfectly!


{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 1, 'CommentCount': 6, 'ContentLicense': 'CC BY-SA 3.0', 'CreationDate': '2014:00:02/16/14', 'FavoriteCount': 1.0, 'PostTypeId': 1, 'Tags': '<c++><algorithm><primes><sieve-of-atkin>', 'Title': 'C++ Sieve of Atkin Returning Several Composites', 'ViewCount': 89, 'id': 21808043, 'user_AboutMe': '', 'user_AccountId': 4027885.0, 'user_DisplayName': 'Thomas141592', 'user_Reputation': 3.0, 'user_Views': 2.0, 'user_id': 3315300.0}}