CODEWITHSUNDEEP
c++performanceloopsmath
user3519448
user3519448

Reputation: 119

Efficient way of finding Primes

I have a loop that goes from 3 to the phi of two prime user-inputted numbers (these numbers can be any length), finds all the prime numbers between the two, and stores them into an array.

My code for the loop:

int coPrimes(int num)
{
    for (int i=3; i<=num; i++)
        if(isPrime(i))
            coprimes.push_back(i);

This loop takes a long period of time to finish. 

Enter a prime number for 'a': 601
Enter a prime number for 'b': 769
a value: 601
b value: 769
product: 462169
phi: 460800
pubKey: 19
privKey: 145515

Process returned 0 (0x0)   execution time : **756.670 s**
Press any key to continue.

I need this loop to work at a faster speed. Is there a more efficient method of performing this action?

P.S. My loop calls another function,isPrime, here is the code for it if anyone wanted it. 

bool isPrime(int num)
{
    bool prime = true;

    if(num < 2)
        prime = true;
    for (int i=2; i<num; i++)
        if (num % i == 0)
            prime = false;
    return prime ;
}

Upvotes: 2

Views: 2081

Answers (5)

Thomas Ahle
Thomas Ahle

Reputation: 31604

They way I read your question is, that you want to find all primes in some range [a,b].

If you have enough memory, the fastest way to do this, is probably using the Sieve of Eratosthenes. Wikipedia has a good demo of how it works:

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

First number in the list is 2; cross out every 2nd number in the list after it by counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):

2  3  x  5  x  7  x  9   x 11  x 13  x 15  x 17  x 19  x 21  x 23  x 25

Next number in the list after 2 is 3; cross out every 3rd number in the list after it by counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):

2  3  x  5  x  7  x  x   x 11  x 13  x  x  x 17  x 19  x  x  x 23  x 25

Next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after it by counting up from 5 in increments of 5 (i.e. all the multiples of 5):

2  3  x  5  x  7  x  x   x 11  x 13  x  x  x 17  x 19  x  x  x 23  x  x

This is faster than checking if each number is a prime, since the outer loop only runs over every prime, and the inner loop runs faster and faster. The sum of reciprocals of primes is loglogn, so in total you get O(nloglogn) time. Much better than your current O(n^2) or O(n^(3/2)) with faster prime checking.

Upvotes: 4

BrainStone
BrainStone

Reputation: 3165

I suggest using the Sieve of Eratosthenes for your problem. But I also see more or less three very simple optimizations that will speed up your code alot!

for (int i=3; i<=num; i += 2)
    if(isPrime(i))
        coprimes.push_back(i);

This will skip every even number. We know they connot be prime. You already doubled your speed! (Not quite be almost).

And here are the next two optimizations:

bool isPrime(int num)
{
    // If your function is only executed from that loop above, delete this statement.
    if(num < 2)
        return false;

    if(!(num % 2))
        return num == 2;

    int limit = sqrt(num);
    for (int i=3; i<=limit; i += 2)
        if (!(num % i))
            // You can stop after you found the first divisor
            return false;

    return true;
}

You don't need the boolean since you never use it anywhere except for the last return. After that you should first of all check if it is divisible by two. If so we can end already. This allows again for skipping all even divisors. Next take the square root of you number to check. I know this is time consuming but it pays of for larger numbers because you don't have to check the majority of the numbers.

With these little optimizations your code will be a lot faster. I guess it should be able to do it in less than 100 seconds (if your previous outcome is over 700).

Upvotes: 2

EchoAce
EchoAce

Reputation: 89

It seems like you might be using this program often, so why don't you try implementing the sieve of Eratosthenes as well as storing your results in a file?

What this would entail is not only adding the primes you find to the vector, but writing the results to a file. This way you may only need to run it once slowly, and in the future you can just check whether phi is greater than the last number in the file. If it isn't, great cause you can just use the numbers in the file. If it is, just start checking from n + 1 to phi, where n is the last prime in the file.

Upvotes: 0

dragosht
dragosht

Reputation: 3275

The performance degradation in your case comes from your primality testing routine. Try this as a first optimization:

bool isPrime(int num)
{
    bool prime = true;

    if(num < 2)
        prime = true;
    for (int i = 2; i < (int)sqrt(num) + 1; i++)
        if (num % i == 0)
            prime = false;
    return prime ;
}

You can find some additional optimization steps for basic primality testing here: http://en.kioskea.net/faq/977-c-language-checking-whether-an-integer-is-a-prime-number

Upvotes: 2

Iulian Popescu
Iulian Popescu

Reputation: 2643

To search for a lot of prime number is better to use sieve of Eratosthenes and wikipedia it's a good start. From there I learned this algorithm.

Upvotes: 1

Related Questions