1

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;
}
user2952566
  • 13
  • 1
  • 1
  • 3
  • 1
    http://en.wikipedia.org/wiki/Primality_test – LeeNeverGup Nov 04 '13 at 12:56
  • well..thats what i have done.primality check for each nuber in the range. but its too slow! – user2952566 Nov 04 '13 at 13:02
  • I meant you can check primality faster. Did you look on this:http://en.wikipedia.org/wiki/Generating_primes ? – LeeNeverGup Nov 04 '13 at 13:04
  • http://en.wikibooks.org/wiki/Efficient_Prime_Number_Generating_Algorithms – jbat100 Nov 04 '13 at 13:15
  • just use any standard segmented sieve algorithm, example: [Fast implementation of the **segmented sieve** of Eratosthenes](http://sweet.ua.pt/tos/software/prime_sieve.html). – jfs Nov 04 '13 at 13:42
  • I implemented a segmented Sieve of Eratosthenes [here](http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes). At the step where its says `output t` you could count the prime instead of writing it. – user448810 Nov 04 '13 at 14:42
  • the standard thing for this kind of problems is to perform an [offset sieve of Eratosthenes](http://stackoverflow.com/a/19641049/849891). Just to make sure the correct terminology: "segmented sieve" refers to continual production of primes by segments. Here you do the base, and an offset segment. – Will Ness Nov 06 '13 at 11:04
  • 2
    there are algorithms which find number of primes below a limit, without finding the primes themselves. This is known as *`pi(N)`*, a [prime counting function](https://en.wikipedia.org/wiki/Prime-counting_function). – Will Ness Nov 06 '13 at 13:50

4 Answers4

10

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.

starblue
  • 55,348
  • 14
  • 97
  • 151
1

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.

jbat100
  • 16,757
  • 4
  • 45
  • 70
  • 2
    *"making the generation of **even 10 digit** verified primes possible within a reasonable amount of time on a PC."* this is just **terrible**. – Will Ness Nov 06 '13 at 10:57
  • 1
    what contribution? please specify, I don't want to have to guess. -- that page is terrible. what's the end result? primes below 2 billion in - "reasonable" time - a code word for 15 minutes / half an hour? sieves go there much faster, and reach much much higher than "even" 2 billion. The word "even" shows how slow it is. The author there had reinvented the [wheel](https://en.wikipedia.org/wiki/Wheel_factorization) - literally; that's great. Wheel or no wheel, sieves are faster. – Will Ness Nov 06 '13 at 13:47
  • aha, I suspected that, but didn't want to assume that. I hope I've clarified now what I meant. – Will Ness Nov 06 '13 at 13:52
  • 1
    He reinvented the wheel, and his wheel is a square. – starblue Nov 07 '13 at 09:12
0

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.

Diego Giagio
  • 1,027
  • 7
  • 7
  • @jbat100 Of course there are faster algorithms. It always depends on the requirements. The Sieve of Eratosthenes algorithm is much faster than the one the OP coded, though. – Diego Giagio Nov 04 '13 at 13:20
  • i have used sieve of eratosthenes to store primes upto 10^6..i need primes upto 10^12. can i use these 10^6 primes to generate furthur primes? – user2952566 Nov 04 '13 at 14:08
  • concept of segmented sieve? – user2952566 Nov 04 '13 at 14:12
  • @jbat100 the Sieve is really the fastest of the simplest. There are ways to calculate pi(N) which are faster but that's not as simple as sieve. and trial division with wheel is slower than segmented (or offset) sieve - which can also be sped up with the use of prime wheel. – Will Ness Nov 06 '13 at 13:55
0

Here is my implementation of Sieve of Erathostenes:

#include <string>
#include <iostream>

using namespace std;

const int k = 110000; //you can change this constant to whatever maximum int you would need to calculate
long int p[k]; //here we would store Sieve of Erathostenes from 2 to k
long int j; 

void init_prime() //in here we set our array
{
    for (int i = 2; i <= k; i++)
    {
        if (p[i] == 0)
        {
            j = i;
            while (j <= k)
            {
                p[j] = i;
                j = j + i;
            }
        }
    }
    /*for (int i = 2; i <= k; i++)
        cout << p[i] << endl;*/ //if you uncomment this you can see the output of initialization...
}

string prime(int first, int last) //this is example of how you can use initialized array
{
    string result = "";
    for (int i = first; i <= last; i++)
    {
        if (p[i] == i)
            result = result + to_str(i) + "";
    }
    return result;
}

int main() //I done this code some time ago for one contest, when first input was number of cases and then actual input came in so nocases means "number of cases"...
{
    int nocases, first, last;
    init_prime(); 
    cin >> nocases;
    for (int i = 1; i <= nocases; i++)
    {
        cin >> first >> last;
        cout << prime(first, last);
    }
    return 0;
}

You can use the Sieve of Erathostenes to calculate factorial too. This is actually the fastest interpretation of the Sieve I could manage to create that day (it can calculate the Sieve of this range in less than a second)

SeriousDude
  • 25
  • 7