CODEWITHSUNDEEP
c++primessieve-of-eratosthenes
user2952566
user2952566

Reputation: 13

fastest method for finding number of prime numbers between two large numbers x and y

here x,y<=10^12 and y-x<=10^6

i have looped from left to right and checked each number for a prime..this method is very slow when x and y are somewhat like 10^11 and 10^12..any faster approach? i hv stored all primes till 10^6..can i use them to find primes between huge values like 10^10-10^12?

for(i=x;i<=y;i++)
{
    num=i;
    if(check(num))
    {
        res++;
    }
}

my check function

int check(long long int num)
{
    long long int i;
    if(num<=1)
        return 0;
    if(num==2)
        return 1;
    if(num%2==0)
        return 0;
    long long int sRoot = sqrt(num*1.0);
    for(i=3; i<=sRoot; i+=2)
    {
        if(num%i==0)
            return 0;
    }
    return 1;
}

Upvotes: 1

Views: 10474

Answers (3)

starblue
starblue

Reputation: 56792

Use a segmented sieve of Eratosthenes.

That is, use a bit set to store the numbers between x and y, represented by x as an offset and a bit set for [0,y-x). Then sieve (eliminate multiples) for all the primes less or equal to the square root of y. Those numbers that remain in the set are prime.

With y at most 1012 you have to sieve with primes up to at most 106, which will take less than a second in a proper implementation.

Upvotes: 10

jbat100
jbat100

Reputation: 16827

This resource goes through a number of prime search algorithms in increasing complexity/efficiency. Here's the description of the best, that is PG7.8 (you'll have to translate back to C++, it shouldn't be too hard)

This algorithm efficiently selects potential primes by eliminating multiples of previously identified primes from consideration and minimizes the number of tests which must be performed to verify the primacy of each potential prime. While the efficiency of selecting potential primes allows the program to sift through a greater range of numbers per second the longer the program is run, the number of tests which need to be performed on each potential prime does continue to rise, (but rises at a slower rate compared to other algorithms). Together, these processes bring greater efficiency to generating prime numbers, making the generation of even 10 digit verified primes possible within a reasonable amount of time on a PC.

Further skip sets can be developed to eliminate the selection of potential primes which can be factored by each prime that has already been identified. Although this process is more complex, it can be generalized and made somewhat elegant. At the same time, we can continue to eliminate from the set of test primes each of the primes which the skip sets eliminate multiples of, minimizing the number of tests which must be performed on each potential prime.

Upvotes: 1

Diego Giagio
Diego Giagio

Reputation: 1057

You can use the Sieve of Eratosthenes algorithm. This page has some links to implementations in various languages: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

Upvotes: 0

Related Questions