value requires 1000000000 bytes, which is more than max-value-size

Question

I am stuck with this problem on spoj.com

http://www.spoj.com/problems/PRIME1/

After reading a bit about prime generation algorithms, I found that "Sieve of Atkins" is the fastest prime generation algorithm. I have partially implemented the algorithm with the help of this tutorial http://www.geeksforgeeks.org/sieve-of-atkin/

When I ran the code, it gave me segmentation fault. After debugging I came to know that this code is not optimal, it uses more memory, storage. Could someone tell me how can I optimise the program. Here is my code snippet. And yeah, it is incomplete.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int sieveOfAtkin(long int limit)
{
    // if limit is either 2 or 3, print them
    if (limit >= 2)
    {
        cout << 2 << endl;
    }

    if (limit >= 3)
    {
        cout << 3 << endl;
    }


    bool sieve[limit];
    for (long int i=0; i<=limit; i++)
        sieve[i] = false;

    for (long int x=1; x<limit; x++)
    {
        for (long int y=1; y<limit; y++)
        {

            long int n = (4*x*x) + (y*y);
            if (n<=limit && (n%12==1 || n%12==5))
                sieve[n] ^= true;

            n = (3*x*x) + (y*y);
            if (n<=limit && (n%12==7))
                sieve[n] ^= true;

            n = (3*x*x) - (y*y);
            if (x>y && n<=limit && (n%12==11))
                sieve[n] ^= true;
        }
    }

    for (long int r=5; r*r<limit; r++)
    {
        if(sieve[r])
        {
            for(long int i=r*r; i<limit; i+=r*r)
                sieve[r] = false;
        }
    }

    for (long int i=5; i<limit; i++)
        if(sieve[i])
            cout << i << endl; 

    return 0;
}

int main(void)
{
    long int x;
    cin >> x;
    sieveOfAtkin(x);
    return 0;
}

For starters, `std:vector` is more memory-efficient. I almost forgot - [this](http://stackoverflow.com/questions/1887097/variable-length-arrays-in-c). — LogicStuff, Jun 14 '16 at 12:55
[using namespace std; is a bad idea](http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-in-c-considered-bad-practice) — Ed Heal, Jun 14 '16 at 14:41
If you are asked to find the primes between 999,999,990 and 1,000,000,000 then finding all the primes less than a thousand million might be considered a waste of time. — rici, Jun 14 '16 at 21:59
@rici yes, currently working on making the changes for upper and lower bounds only — Lakshmikant Deshpande, Jun 15 '16 at 00:44

score 4 · Accepted Answer · edited May 23 '17 at 12:22

4

First, it is an internet myth that the Sieve of Atkin is faster than the Sieve of Eratosthenes. The Sieve of Atkin is faster under certain constraints, but the Sieve of Eratosthenes is faster in general and is the sieve chosen by mathematicians who actually use it to investigate prime numbers.

Second, when the sieve gets too large to fit in memory you can segment the sieve. See this answer for details.

edited May 23 '17 at 12:22

Community

1
1

answered Jun 14 '16 at 16:54

user448810

17,381
4
34
59

It worked. I calculated primes upto 32000, as ~31622 is square root of the maximum number I need. i.e. 1 billion – Lakshmikant Deshpande Jun 24 '16 at 10:30
Thank you ! Though my solution was not so optimal, it worked :) – Lakshmikant Deshpande Jun 24 '16 at 10:31

value requires 1000000000 bytes, which is more than max-value-size

1 Answers1