1

I have implemented Sieve of Eratosthenes in c++ but the code crashes for input greater than 10^10.Compiler show signal 11(SIGSEV).It's because of the global array bool a[5000000000000000];.To check odd numbers upto 10^16, I took the array size as (10^16)/2 = 5 * 10^15. How to reduce the space ? There is an answer for this question How do i reduce the space complexity in Sieve of Eratosthenes to generate prime between a and b? I tried accordingly but my program crashes.Could anybody provide implementation details to fix it ?

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

long long unsigned n,sqN;
bool a[5000000000000000];
long long int sieve_of_Eratosthenes();
int main()
{
    cout<<"Enter upper bound to generate prime upto:"<<endl;
    cin>>n;
    long long int count = sieve_of_Eratosthenes();
    cout<<"Total = "<<count<<endl;
    return 0;
}
long long int  sieve_of_Eratosthenes()
{
    long long unsigned i,j,count = 0;
    sqN = (long long unsigned) sqrt(n);
    for(i=3; i<=sqN; i+=2)
    {
        if(a[i/2]==true)
        {
            continue;
        }
        for(j = i*i; j<=n; j+=(2*i))
        {
            a[j/2] = true;
        }
    }
    if(n>=2)
    {
        count++;
        cout<<2<<endl;
    }
    for(i=3; i<=n; i+=2)
    {
        if(a[i/2]==false)
        {
            cout<<i<<endl;
            count++;
        }
    }
    return count;

}
Community
  • 1
  • 1
Tavij
  • 98
  • 7
  • `vector` may be implemented in such a way that you can get incredible size, but at a performance cost packing and unpacking bits. Profile to see if it's the right solution for you. – user4581301 Aug 29 '16 at 17:50
  • 2
    I'd like to see the computer that can allocate this amount of memory on the stack or anywhere. – fuenfundachtzig Aug 29 '16 at 17:55
  • 3
    Guys,he has that as a global, so unless you're dealing with a truly *strange* implementation, it would never be on the stack. – Jerry Coffin Aug 29 '16 at 18:06
  • 4
    I got an idea to use `std:bitset` in c++. It will surely reduce space. How's about trying it ? – Tavij Aug 29 '16 at 18:15
  • 1
    Google tells me that will take 5 Petabytes to store the array of bool. Hmm. Better reduce the problem size.. – drescherjm Aug 29 '16 at 18:39

2 Answers2

4

You can't allocate this much memory space in any computer which is not a supercomputer. If you just want to generate primes in a given range {say,(a,b) where a <= b <= 10^16} , you can simply use Sieve of Erathosthenes to store primes upto sqrt(10^16) and then apply Segmented Sieve.

Benefits of using segmented sieve are:

  • reduced time complexity
  • no need to waste precious memory. You can easily generate primes for small ranges with a lot less space
Tushar
  • 51
  • 5
  • You probably can't allocate that much memory even on a supercomputer. Most supercomputers these days are clusters, where each node has its own memory. It might be possible to create a chunk of virtual memory that big, but as far as I know that's not commonly done. – Keith Thompson Aug 29 '16 at 19:38
2

Even if you use single bit per odd number, you would need 6.25e14 = 625 terabytes to store it. You could possibly do it by mapping some big disk array to memory, or use RAM of a supercomputer... But unless you have such hardware I don't think you can use regular sieve of Eratosthenes with such big numbers.

michalsrb
  • 4,703
  • 1
  • 18
  • 35