# Prime number finder

There's another exercise from Thinking in C++.
This time it asks this:

Write a program that uses two nested for loops and the modulus operator (%) to detect and print prime numbers (integral numbers that are not evenly divisible by any other numbers except for themselves and 1).

And this is what I think:

// finds all prime numbers between 2 and a number given in input.
#include <iostream>
using namespace std;

int main(int argc, char* argv[]) {
cout << "How many prime numbers do you want to print? ";
int n;
cin >> n;

int i, j;
bool flag = true;
for(i = 2; i <= n; i++) {
for(j = 2; j <= i; j++) {
if((i % j) == 0) {
if(i == j)
flag = true;
else {
flag = false;
break;
}
}
}

if(flag)
cout << "Prime: " << i << endl;
}
}


It works perfectly, but I'd know what do you think about. Thanks for the feedback!

• for(j = 2; j <= i; j++) should be for(j = 2; j * j < i; j++) – Alexandre C. Aug 11 '11 at 23:23
• To check if n is a prime you only have to check divisibility by up to sqrt(n). You have excess computations. – Jared Ng Aug 11 '11 at 23:23

Forgive me, I'm a C# developer, I like descriptive terms :)

As Alexandre mentioned, the sqrt is key to minimize computations. Great heuristic. Another heuristic you can use is every other number will not be prime, as it will be divisible by 2. Then to expand on this heuristic, you can say that no odd numbers are divisible by even numbers and therefore may skip every other number as your divisible test number.

for(int mightBePrime = 3; mightBePrime <= upperLimitToCheck; mightBePrime += 2)
{
bool foundAPrime = true;
for(int divisorToCheckPrime = 3; divisorToCheckPrime * divisorToCheckPrime <= mightBePrime ; divisorToCheckPrime += 2)
{
if(mightBePrime % divisorToCheckPrime == 0)
{
foundAPrime = false;
break;
}
}
}

• +1 for best answer, though to be really pedantic, this does miss the number 2 :-) – Steve Mallam Aug 12 '11 at 8:44
• I remember doing some Euler projects where the modulus was actually inducing a fair amount of overhead. If your set is very large you may want to consider a simple isOdd = num & 1. That said... this was years ago and who's to say I wasn't stupidly running a debug build? A decent compiler should produce identical code for either... but you may want to check. – Ed S. Aug 12 '11 at 18:36

This is sloppy coding. You should not use it. It is best to fully qualify stuff from the std namespace. Its not that hard or long.

using namespace std;


I would put a "\n" on the end of the line. It makes the questions on the terminal look like the question is on one line and your answer is on the next which in my mind makes it easier to read.

    cout << "How many prime numbers do you want to print? ";


Single letter variables names is again slopy.
Your variable names should be descriptive. So readers can see your intention. As a side affect it makes looking for the variable easy. Especially if you use an editor that is scriptable and want to automate some task on the variable.

    int n;
cin >> n;


Personally I don't like the '{' at the end of the line. But I realize that is a style thing so I don;t care if other people do it like this.

    for(i = 2; i <= n; i++) {


Other have already pointed out that the inner loop can be optimized a bit.

        for(j = 2; j <= i; j++) {


This test should never be required.
It just means that you are doing extra work.

                if(i == j)


Try this:

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

struct PrimeTest
{
PrimeTest(int val)
: value(val)
{}
bool operator()(int test) const  { return value%test == 0;}
int value;
};

int main()
{
std::vector<int>        primes;
int                     maxCount;

std::cout << "Check how many numbers?\n";
std::cin >> maxCount;

for(int primeTest = 2; primeTest <= maxCount; ++primeTest)
{
// There is a loop hidden inside here.
if (std::find_if(primes.begin(), primes.end(), PrimeTest(primeTest)) == primes.end())
{   primes.push_back(primeTest);
}
}
std::copy(primes.begin(), primes.end(), std::ostream_iterator<int>(std::cout, ", "));
}


But since the question explicitly asked for two loops:
You can write the loop like this.

    for(int primeTest = 2; primeTest <= maxCount; ++primeTest)
{
std::vector<int>::iterator loop = primes.begin();
TestPrime       test(primeTest);
for(;loop != primes.end(); ++loop)
{
if (test(*loop))
{   break;
}
}
if (loop == primes.end())
{   primes.push_back(primeTest);
}
}


Technically you don't need to test all the numbers less than the number you are testing. Some have pointed out the easy optimization of only testing up to the square root of the number. But an even better solution is to only test the primes below your number.

• Better still is to only test against primes up to the square root of the number. Then again, if you're going to find all the primes up to some limit, you should normally use the sieve of Eratosthenes (even though that doesn't fit the assignment). – Jerry Coffin Aug 12 '11 at 9:27
• @Jerry: That is the next optimization. But only checking primes reduces the set of values by such a huge number compared to just checking upto the root of the value I though it was a great improvement. – Martin York Aug 12 '11 at 14:06
• There is no reason to fully quality everything in std for a simple throwaway program. That's ridiculous. Even then your advice is bad; just use using std::cin, you don't have to fully qualify it every time. – Ed S. Aug 12 '11 at 22:29
• @Ed S: Sure you can be lazy. But habits become hard to break. You do not want to get in the habit of using bad practice because when you write a more complex application you don;t want to use bad habits or sloppy technique as this is going to cost you one day with a big break. I always fully qualify everything in standard. Its not as if it takes any more work. If it is a short program say less than a page I'll probably save typing anyways as I would have to use 5 objects in the standard namespace before it becomes more expansive than typing 'using namespace std;' (21 characters including) – Martin York Aug 13 '11 at 0:18
• @Ed S: In fact in the above code it is 1 character shorter to prefix everything with std:: I also agree that pull things in selectively is also OK (as long as you scope the inclusion). So using std::cin but I rarely bother. – Martin York Aug 13 '11 at 0:21

The question at the beginning is misleading. n is an upper bound for the primes to be printed, not the number of primes. You should change it to

cout << "Enter an upper bound for the prime numbers to print: ";


If you're finding a single prime number, looping through all the numbers up to it's square root is good. But if you're trying to find every prime up to a certain limit, then do as follows. Keep a list of each prime you find, then, when checking a new number, only check it against the previously found primes, up to it's square root. So, something like this:

std::vector<int> primes;
for(int i=2; i<=n; ++i)
{
bool is_prime = true;
int sq = sqrt((long double)i);
for (int j=0; j<primes.size() && primes[j] <= sq; ++j)
{
if (i % primes[j] == 0)
{
is_prime = false;
break;
}
}
if (is_prime) primes.push_back(i);
}


In addition to everything already mentioned, you're not checking whether the user inputs a valid integer. As suggested by the C++ FAQ:

int max_prime;
while ((std::cout << "Enter an upper bound for the prime numbers to print: ")
&& !(std::cin >> max_prime)) {
std::cout << "That is not a valid number. ";
std::cin.clear();
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}


for(j = 2; j <= i; j++) should be for(j = 2; j * j <= i; j++). You only need to test for divisors less than the square root of i (if there is a divisor greater than sqrt(i), there is one less than sqrt(i)).

The loop should therefore read:

for(i = 2; i <= n; i++)
{
bool flag = true;

for(j = 2; j * j <= i; j++)
{
if(i % j != 0)
{
flag = false;
break;
}
}

if (flag) cout << "Prime: " << i << endl;
}

• Your code doesn't works... – unNaturhal Aug 11 '11 at 23:40
• @unNaturhal: Care to tell us anything more? – Peter C Aug 12 '11 at 2:32
• @alpha123: It prints 2, 3, 4, 5, 6, 8 if you give 10 in input. – Overflowh Aug 12 '11 at 14:16

Here is my Java code to create primes, which should be easily modified to match c++ needs:

public static boolean [] createPrimes (final int MAX)
{
boolean [] primes = new boolean [MAX];
// make only odd numbers are candidates...
for (int i = 3; i < MAX; i+=2)
{
primes[i] = true;
}
// ... except the 2
primes[2] = true;

// ... iterate in steps of 2
for (int i = 3; i < MAX; i+=2)
{
/*
If a number z is already eliminated, (like 9),
because it is a multiple, (of 3), then all
multiples of that number are already
eliminated too.
*/
if (primes[i])
{
int j = 2 * i;
while (j < MAX)
{
if (primes[j])
primes[j] = false;
// in this inner loop *)
j+=i;
}
}
}
return primes;
}


In the inner loop, you even may jump in steps of i, because after eliminating multiples of 3*x (3*5, 3*7, 3*11, ...) you don't need to eliminate multiples like 5*3, the 3-times-something are already gone. The same if you reach 7: 7*3 is already gone as 3*7, and 7*5 as 5*7. Only multiples higher than 7 should be visited/tested.