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

• phuclv: to check for a prime, no need to loop all from 2 to n, just odd numbers from 2 to sqrt(n) is enough

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.

• leetNightshade: To be consistent all functions should not have Egyptian brackets, or all should. Right now main and isPrime are inconsistent in that regard.
• Loki Astari: @leetNightshade: What are Egyptian brackets. Not heard that term before. Though I agree with the general comment.
• Vality: @LokiAstari Egyptian brackets are placing the opening curly on the same line as the function name eg: foo(){ as opposed to foo()\n{ (using \n to signify new line as I cant put one in a comment.)
• jwenting: @Vality hmm, weird name for standard K&R bracing. But indeed not proper for C++.
• Vality: @jwenting I am not sure where the term came from, I think it is the term used for that style of brackets in Java where K&R style would have no meaning. However it is easy enough to guess what is meant in C also. Personally I always prefer the next line as else my eyes have trouble matching pairs of brackets but it is a valid style in some conventions.

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.

• Anonymous: Beware: iostreams vs. stdio is controversial among C++ programmers. Definitely avoid scanf, though.

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.