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

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

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

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.

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

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

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.

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