Prime number finder

Question

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!

Answer 1

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;
    }
  }
}

Answer 2

What I think about your code:

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.

Answer 3

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: "; 

Answer 4

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);
}

Answer 5

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');
}

Answer 6

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;
}

Answer 7

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.