increase code speed

lmvent · 10-20-2005, 07:39 PM

I was given this code:

Code:

#include <iostream>

using namespace std;

int main(void)
{   cout << "Input the largest positive integer to check: ";
    unsigned int maxN;
    cin >> maxN;
    unsigned int nPrimes = 0;
    for (int i = 2; i <= maxN; i = i + 1)
    {   bool isPrime = true;
        for (int j = 2; j < i; j = j + 1)
        {   if (i%j == 0)
            {   isPrime = false;
            }
        }
            if (isPrime)
            {   //cout << i << " ";
                nPrimes = nPrimes + 1;
            }
    }
    cout << "\n\nThere are " << nPrimes << " prime numbers <= " << maxN << "\n";
    return 0;
}

My assignment is to make this code go faster and find the number of prime numbers smaller than a given integer. I'm not asking for the answer! I would just like a hint if anyone knows what I should do. I know I need to use vectors and our professor told us a hint that if you cancel all of the multiples of the prime numbers below the square root of the maximum number, the rest are primes, but I don't know how to put that into my code. Any hints for me??

rshaw · 10-20-2005, 07:45 PM

google for 'sieve of Eratosthenes'

lowpro2k3 · 10-20-2005, 11:45 PM

Quote:

Originally posted by lmvent
Any hints for me??

First figure out the algorithm, on paper, then it will be trivial to implement in code

lmvent · 10-21-2005, 08:37 AM

Do i need nested for loops??

misterscorp · 10-21-2005, 09:42 AM

i think a pseudocode will go like this..

#define N 20 /* Use small number for testing*/
main() {
int arrIntegers[N]; /* array of Integers*/
for(i=0;i<n;i++)
initialize arrIntegers[i];
for(i=2;i<n;i++)
mark the multiples of i;
/* this marking can be done with
one 'for' and one 'if' stmt */
for(i=2;i<n;i++)
print the unmarked entries of it;
}
try to implement this ....

lmvent · 10-21-2005, 10:37 AM

sorry I forgot to mention I can't use arrays. I am in a first year class and we haven't gotten there yet.

NineBreaker104 · 10-21-2005, 12:11 PM

Quote:

Originally posted by lmvent

Code:

    for (int i = 2; i <= maxN; i = i + 1)
    {   bool isPrime = true;
        for (int j = 2; j < i; j = j + 1)
        {   if (i%j == 0)
            {   isPrime = false;
            }
        }
            if (isPrime)
            {   //cout << i << " ";
                nPrimes = nPrimes + 1;
            }
    }

The key part is this section of the code. What you are essentially doing is checking to see if i is divisible by j, where j are numbers between 2 and the value of i. The trick to this problem is that when you are trying to see if a number is prime, you don't have to check from 2 to the value of i. You can only have to check from 2 to the squartroot of i. Example:

i = 33. Your current code divides 33 with every value from 2 to 32. However, all you have to do is divide with every value from 2 to the squrtroot of 33 (it rounds down to 5). Why? Because we know that 33 is divisible by 3, which makes it a non-Prime value.

Bottom line, you don't have to check from 2 to the value of i to see if a number is prime or not. So, instead, find the squareroot of i, and check from to 2 that new value.

I hope I didn't explain it too confusingly.

lmvent · 10-21-2005, 03:12 PM

wow that definitely helps a lot! Thanks! If I need more help after I work on it, I'll be back

lmvent · 10-25-2005, 10:50 PM

Code:

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main(void)
{   cout << "Input the largest positive integer to check: ";
    unsigned int maxN;
    cin >> maxN;
    int n = (int)sqrt(static_cast<float>(maxN));
    vector<int>primes;
    for (int i = 2; i <= maxN; i = i + 1)
    {   primes.push_back(i);
        for (int j = 2; j < i && j <= n; j = j + 1)
        {   if (i%j == 0)
            {   primes.pop_back();
                j = n + 1;
            }
        }
    }
    for (int i = 0; i < primes.size(); i = i + 1)
    {   cout << primes[i] << " ";
    }
    cout << "\n\nThere are " << primes.size() << " prime numbers <= " << maxN << "\n"; 
    return 0;
}

This is my code now and runs about 1000 times faster than my professor's, but to get full credit it has to be more than 5000 times faster. He said to get it that fast the algorithm has to be redesigned and vectors need to be used in a clever way. Any hints now??

enemorales · 10-26-2005, 04:10 AM

We are now supposed to do your homework, so I'll only give you a hint: save the numbers you already now that are primes and use them!

bigearsbilly · 10-26-2005, 05:37 AM

remember you only need to check odd numbers.

Orkie · 10-26-2005, 08:19 AM

2 is a prime number.

bigearsbilly · 10-26-2005, 08:23 AM

hmm, do you think maybe there are any more?

lmvent · 10-26-2005, 10:27 AM

Code:

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main(void)
{   cout << "Input the largest positive integer to check: ";
    unsigned int maxN;
    cin >> maxN;
    int n = (int)sqrt(static_cast<float>(maxN));
    vector<int>primes;
    for(int i = 2; i <= n ; i = i + 1)
    {   primes.push_back(i);
        for(int j = 2; j <= (int)sqrt(static_cast<float>(n)) && j < i; j = j + 1)
        {   if (i%j == 0)
            {   primes.pop_back();
                j = n + 1;
            }
        }
    }
    int m = primes.size() - 1;
    for(int i = n + 1; i <= maxN; i = i + 1)
    {   primes.push_back(i);
        for(int j = 0; j <= m; j = j + 1)
        {   if(i%primes[j] == 0)
            {   primes.pop_back();
                j = n + 1;
            }
        }
    }
    //for(int j = 0; j < primes.size(); j = j + 1)
    //{   cout << primes[j] << " ";
    //}
    cout << "\n\nThere are " << primes.size() << " prime numbers <= " << maxN << "\n";
    return 0;
}

Okay, this is what I have now. It is a little bit faster, but not quite fast enough. He said the algorithm needs to be redesigned, but I can't think of another way to check if a number is prime. Any hints on that??

jtshaw · 10-26-2005, 12:12 PM

I can think of two things right away.. first off, your outer loop should probably increment by 2 instead of 1 (should make it take half the time... because you know 2 is the only even prime). Second thing... if your afraid the vector operation is costly.. Check to see if the number is prime before you push it on the vector. This will save you many vector operations if maxN is a large number.