# Prime number generator in C++

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

• to check for a prime, no need to loop all from 2 to n, just odd numbers from 2 to sqrt(n) is enough – phuclv Apr 8 '14 at 3:04

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.

• To be consistent all functions should not have Egyptian brackets, or all should. Right now main and isPrime are inconsistent in that regard. – leetNightshade Apr 7 '14 at 22:08
• @leetNightshade: What are Egyptian brackets. Not heard that term before. Though I agree with the general comment. – Martin York Apr 7 '14 at 23:30
• @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.) – Vality Apr 8 '14 at 0:15
• @Vality hmm, weird name for standard K&R bracing. But indeed not proper for C++. – jwenting Apr 8 '14 at 12:01
• @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. – Vality Apr 8 '14 at 12:10
• 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.

• Beware: iostreams vs. stdio is controversial among C++ programmers. Definitely avoid scanf, though. – Anonymous May 13 '14 at 20:04

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 = false;
primes = 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
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;
}


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.