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 
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Are you new to LinuxQuestions.org? Visit the following links:
Site Howto 
Site FAQ 
Sitemap 
Register Now
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQrelated cookies.

Introduction to Linux  A Hands on Guide
This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.
Click Here to receive this Complete Guide absolutely free. 



10202005, 07:39 PM

#1

LQ Newbie
Registered: Sep 2005
Posts: 24
Rep:

increase code speed
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??



10202005, 07:45 PM

#2

Senior Member
Registered: Apr 2001
Location: Perry, Iowa
Distribution: Mepis , Debian
Posts: 2,694
Rep:

google for 'sieve of Eratosthenes'



10202005, 11:45 PM

#3

Member
Registered: Oct 2003
Location: Canada
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



10212005, 08:37 AM

#4

LQ Newbie
Registered: Sep 2005
Posts: 24
Original Poster
Rep:

Do i need nested for loops??



10212005, 09:42 AM

#5

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<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 ....



10212005, 10:37 AM

#6

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.



10212005, 12:11 PM

#7

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 nonPrime 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.



10212005, 03:12 PM

#8

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



10252005, 10:50 PM

#9

LQ Newbie
Registered: Sep 2005
Posts: 24
Original Poster
Rep:

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??



10262005, 04:10 AM

#10

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!



10262005, 05:37 AM

#11

Senior Member
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Debian, Mint, Puppy
Posts: 3,269
Rep:

remember you only need to check odd numbers.



10262005, 08:19 AM

#12

Member
Registered: Mar 2005
Distribution: Breezy Badger
Posts: 248
Rep:

2 is a prime number.



10262005, 08:23 AM

#13

Senior Member
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Debian, Mint, Puppy
Posts: 3,269
Rep:

hmm, do you think maybe there are any more?



10262005, 10:27 AM

#14

LQ Newbie
Registered: Sep 2005
Posts: 24
Original Poster
Rep:

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??



10262005, 12:12 PM

#15

Senior Member
Registered: Nov 2000
Location: Seattle, WA USA
Distribution: Ubuntu @ Home, RHEL @ Work
Posts: 3,892
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.



Thread Tools 
Search this Thread 


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT 5. The time now is 01:07 AM.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.

Latest Threads
LQ News

