Prime number generator in C++

Question

I am slowly learning C and C++, and decided after a few lessons to dive in myself without any help. I developed this prime number generator. It seems fast, but I'm wondering if I'm following the best practices for C++, or if I am missing anything important.

#include "stdafx.h"
#include "stdio.h"
bool checkPrime(int Number);

int _tmain(int argc, _TCHAR* argv[])
{
    int currentNum;
    currentNum = 2;
    do {
        if (checkPrime(currentNum)) {
            printf("%d ", currentNum);
        }
        currentNum++;
    } while (1 == 1);
    return 0;
}

bool checkPrime(int Number){
    for (int a = 2; a < Number; a++){
        if (Number % a == 0) {
            return false;
        }
    }
    return true;
}

Answer 1

A few things in addition to what @Jamal and @200_success already wrote:

• g++ on Mac OS X won't compile this code, because of #include "stdafx.h" and the int _tmain(int argc, _TCHAR* argv[]) signature. It's good to keep your code portable, unless you have a special reason not to. g++ can compile if you drop the stdafx.h import and if change the main declaration.

• ... and since you're not using the arguments of main, you could just declare without any args: int main() { ... }.

• As you already used true in the checkPrime function, why not use it in the infinite while loop in main, instead of 1 == 1.

• This may be a matter of taste, but I think while (true) { ... } is generally more readable and intuitive than do { ... } while (true).

• ... actually, as @200_success pointed out, a for (int currentNum = 2; ; currentNum++) { ... } loop would be even better: this way currentNum is declared in the block where it is used, eliminating potential side effects, and the counter is a natural element in a for loop. Notice the empty terminating condition, making this an infinite loop.

• In checkPrime you named the variable int Number, but the common convention is to not capitalize variable names, use simply int number instead.

• As @leetnightshade pointed out, place the opening curly either always on the same line as the function name ("Egyption brackets"), or always on the next line.

Suggested implementation

#include <iostream>

bool isPrime(int number)
{
    for (int a = 2; a < number; a++) {
        if (number % a == 0) {
            return false;
        }
    }
    return true;
}

int main()
{
    for (int currentNum = 2; ; currentNum++) {
        if (isPrime(currentNum)) {
            std::cout << currentNum << " ";
        }
    }
}

This compiles with g++ without warnings and runs fine in Mac OS X and GNU/Linux. I would hope it works as expected in Windows too.

Answer 2

• In C++, you should now use std::cout and std::cin instead of printf() and scanf() respectively. These are found in <iostream>, and you'll no longer need <stdio.h>.

  Example of std::cout:

  int number = 1;
  std::cout << "Number: " << number;
  

  Example of std::cin:

  int number;
  std::cin >> number;
  

• currentNum just needs to be initialized, not declared and then assigned:

  int currentNum = 2;
  

• The do while loop condition should just be 1, not 1 == 1. This still equates to true.

• You can put main() below every function, eliminating the need for function prototypes since it will already know the existence of these functions.

• You don't need return 0 at the end of main(). This is a special case in that the compiler will automatically insert return 0 as reaching this point always indicates a successful termination.

Answer 3

One thing you might want to look at is more efficient code. You're running a loop for each number you want to check. Using a Sieve of Eratosthenes means you do all your looping once and the index of the vector returns true or false according to whether it's prime:

#include <iostream>
#include <vector>
#include <cmath>

std::vector<bool> MakePrimes(int upperlimit)
{
    int bound = (int) floor(sqrt(upperlimit));
    upperlimit++;
    std::vector<bool> primes(upperlimit, true);

    primes[0] = false;
    primes[1] = false;
    //Since 2 is a special case if we do it separately we can optimize the rest since they will all be odd
    for(int i = 4; i < upperlimit; i += 2)
    {
        primes[i] = false;
    }
    //Since the only ones we need to look at are odd we can step by 2
    for (int i = 3; i  <= bound; i += 2)
    {
        if (primes[i]) 
        {
            //Since all the even multiples are already accounted for we start at the first one 
            //and skip to every other multiple
            for (int j = i*i; j < upperlimit; j += i * 2)
            {
                primes[j] = false;
            }
        }
    }
    return primes;
}
int main()
{
    int limit = 1000;
    std::vector<bool>checkPrime = MakePrimes(limit);
    int currentNum = 1;
    while (currentNum++ < limit)
    {
        if (checkPrime[currentNum]) 
            std::cout << currentNum << "\n";
    } 
    return 0;
}

Answer 4

This loop…

int currentNum;
currentNum = 2;
do {
    if (checkPrime(currentNum)) {
        printf("%d ", currentNum);
    }
    currentNum++;
} while (1 == 1);

… would be better written as a for loop:

for (int currentNum = 2; /* TODO: fix overflow */ ; currentNum++) {
    if (checkPrime(currentNum)) {
        printf("%d ", currentNum);
    }
}

For readability, checkPrime() should be renamed isPrime(). Its parameter should be named number (lowercase).

You are using a brute-force trial division algorithm. That works, but when you want a list of many prime numbers, the Sieve of Eratosthenes is a much more efficient algorithm.