CODEWITHSUNDEEP
carrayssize
Ritik Raj
Ritik Raj

Reputation: 21

Get an array of size as big as 10^12 in C

I have to find prime numbers between two given numbers a and b, both of them ranging between 1 and 10^12. To do this, I am using a Sieve of Eratosthenes. How can I get such a big array? Exceeding the size 10^6 gives an error.

Upvotes: 0

Views: 57

Answers (4)

chux
chux

Reputation: 153547

to find prime numbers between two given numbers a and b, ... between 1 and 10^12. ... using a Sieve of Eratosthenes.

Algorithm:

To find determine if a number is a prime, the classic approach is to attempt division of all primes 2 ... sqrt(n).

So create a Sieve of Eratosthenes: byte/bit wise flags in the range [0 ... 10^6].

Then test each value [a ...b] against the primes in the array.

So in the end only an array of 1,000,000 is needed.

Upvotes: 1

Tavij
Tavij

Reputation: 98

You can get upto 10^8 by dynamically allocating memory by pointer,like: int *p=(int*) malloc(sizeof(int)*100000000) code:

#include <stdio.h>
#include <stdlib.h>
main()
{
    int *p=malloc(sizeof(int)*100000000);
    p[5]=147;
    printf("%d\n",p[5]);
}

Sieve of Eratosthenes require only sqrt(input array element) sized array.For example Sieve of Eratosthenes needs only a[10] for 100 numbers. Sieve of Eratosthenes implementation in C++ below:

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;
void same(int);
void creat(int);
vector< int>v;
int main()
{
    int a,b,c,i,root,temp;
    cin>>a;
    while(a--)
    {
        cin>>b>>c;
        if(b==c)
        {
            same(b);
            continue;
        }
        temp=b;

        if(b%2==0 )
        {
            if(b==2) {b=3;}
            else
                ++b;
        }

        if (b==1)
        {
            b=3;
        }

        if(temp==2||temp==1||temp==0)
        {
            cout<<2<<endl;
        }
        creat((int)sqrt(c));
        for(i=b; i<=c; i+=2)
        {
            int flag=1;
            root=(int)sqrt(i);
            for(auto j=v.begin();*j<=root && j!=v.end(); ++j)
            {
                if(i%(*j)==0)
                {
                    flag=0;
                    break;
                }
            }
            if(flag)
            {

                cout<<i<<endl;

            }
        }

        cout<<endl;
        v.clear();

    }
    return 0;
}
void same(int n)
{
    if(n==1) return ;
    int rot=(int)sqrt(n);
    for(int i=3; i<=rot; i+=2)
    {
        if(n%i==0)
        {
            return ;
        }
    }
    cout<<n<<endl;
}

void creat(int n)
{

    const int h=n/2;
    int a[h+1],i,j;
    for( i=0; i<=h; i++)
    {
        a[i]=0;
    }

    int r=(int)sqrt(n);
    for(i=3; i<=r; i+=2)
    {
        if(a[i/2]==0)
        {
            for(j=i*i; j<=n; j+=2*i)
            {
                a[j/2]=1;
            }
        }
    }
    for(i=3; i<=n; i+=2)
    {
        if(a[i/2]==0)
        {
            v.push_back(i);
        }
    }
}

Input:

Number of test case lower range upper range

1 1 100 Output: Prime numbers from 1 to 100

Upvotes: 0

Felype
Felype

Reputation: 3136

As said here, you need a lot of RAM (and, of course 64-bit OS) for that kind of allocation. You can resort to a different algorithm, like this one for instance:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

bool isPrime(unsigned long long n) {
    if (n == 2 || n == 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    unsigned long long check = (n + (n % 3)) / 3;
    while (check>3) {
        if (n % check == 0)
            return false;
        check-=2;
    }
    return true;
}

int main(int argc, char** argv) {
    for (unsigned long long l = 2; l < ULLONG_MAX; l++)
    {
        if (isPrime(l))
            printf("%d, ", l);
    }
}

Upvotes: 0

Martin Vidner
Martin Vidner

Reputation: 2337

Please quote the exact error. If you do have enough memory, the code should compile just fine.

But chances are, you do not have the terabytes of memory this would need. So you should probably think about a better algorithm that trades some memory space for some execution time.

Upvotes: 0

Related Questions