Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org increase code speed
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 10-20-2005, 08:39 PM #1 lmvent LQ Newbie   Registered: Sep 2005 Posts: 24 Rep: increase code speed I was given this code: Code: ```#include 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??
 10-20-2005, 08:45 PM #2 rshaw Senior Member   Registered: Apr 2001 Location: Perry, Iowa Distribution: Mepis , Debian Posts: 2,692 Rep: google for 'sieve of Eratosthenes'
10-21-2005, 12:45 AM   #3
lowpro2k3
Member

Registered: Oct 2003
Distribution: Slackware
Posts: 340

Rep:
Re: increase code speed

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

 10-21-2005, 09:37 AM #4 lmvent LQ Newbie   Registered: Sep 2005 Posts: 24 Original Poster Rep: Do i need nested for loops??
 10-21-2005, 10:42 AM #5 misterscorp LQ Newbie   Registered: Oct 2005 Posts: 7 Rep: 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
 10-21-2005, 11:37 AM #6 lmvent LQ Newbie   Registered: Sep 2005 Posts: 24 Original Poster Rep: sorry I forgot to mention I can't use arrays. I am in a first year class and we haven't gotten there yet.
10-21-2005, 01:11 PM   #7
NineBreaker104
Newbie

Registered: Oct 2005
Posts: 1

Rep:
Re: increase code speed

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.

 10-21-2005, 04:12 PM #8 lmvent LQ Newbie   Registered: Sep 2005 Posts: 24 Original Poster Rep: wow that definitely helps a lot! Thanks! If I need more help after I work on it, I'll be back
 10-25-2005, 11:50 PM #9 lmvent LQ Newbie   Registered: Sep 2005 Posts: 24 Original Poster Rep: Code: ```#include #include #include 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(maxN)); vectorprimes; 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??
 10-26-2005, 05:10 AM #10 enemorales Member   Registered: Jul 2004 Location: Santiago, Chile Distribution: Ubuntu Posts: 410 Rep: 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!
 10-26-2005, 06:37 AM #11 bigearsbilly Senior Member   Registered: Mar 2004 Location: england Distribution: FreeBSD, Debian, Mint, Puppy Posts: 3,314 Rep: remember you only need to check odd numbers.
 10-26-2005, 09:19 AM #12 Orkie Member   Registered: Mar 2005 Distribution: Breezy Badger Posts: 248 Rep: 2 is a prime number.
 10-26-2005, 09:23 AM #13 bigearsbilly Senior Member   Registered: Mar 2004 Location: england Distribution: FreeBSD, Debian, Mint, Puppy Posts: 3,314 Rep: hmm, do you think maybe there are any more?
 10-26-2005, 11:27 AM #14 lmvent LQ Newbie   Registered: Sep 2005 Posts: 24 Original Poster Rep: Code: ```#include #include #include 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(maxN)); vectorprimes; for(int i = 2; i <= n ; i = i + 1) { primes.push_back(i); for(int j = 2; j <= (int)sqrt(static_cast(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??
 10-26-2005, 01:12 PM #15 jtshaw Senior Member   Registered: Nov 2000 Location: Seattle, WA USA Distribution: Ubuntu @ Home, RHEL @ Work Posts: 3,892 Blog Entries: 1 Rep: 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.