# Optimizing simple prime number function test

For my first basic project with functions, I wanted to make a program that would allow you to input a number, and it would output whether it was prime or not. For the most part, it's functional and working.

How can I optimize it to be more efficient? How can I make my code more readable for the next person? What are some good programming techniques?

#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <math.h>

using namespace std;
int PrimeTest(int x);

int main()
{
int X = 0;
cout << "Enter a number ";
cin >> X;
cout << "\n\n\n\t\t\t";
if (PrimeTest(X) == 1)
{
cout << X << " is prime";
}
else
{

cout << X << " is NOT prime";
}

cout << "\n\n\n\t\t\t";
return 0;
}

int PrimeTest(int x)
{
int b = 2;
while (b < x)
{
if (x % b == 0)
{
}

b++;
}
}


• You have both <cmath> and <math.h>, but you only need the former. The latter is a C library.

• You can have main() at the bottom, allowing you to eliminate the function prototype.

• Do not use single-character variable names (except for simple loop counters, which can be simple). They are hard to understand for others, and may even leave you confused in the future, especially if you expand on the program quite a bit.

As such, X should be renamed to something like number.

• PrimeTest() should return bool, not int. Returning an int is more common in C, but is not done in C++ (it's only done in main(), but it is special). You'll then return either true or false and compare them as such. This will also eliminate the need for Answer.

• The final output can be simplified to a single-line ternary (?:) statement:

std::cout << X << " is " << ((PrimeTest(X)) ? "prime" : "NOT prime");


This is essentially a shorter way of writing an if/else statement, but is best done with simple cases such as this one. If you'll ever need to expand on these conditions, then it would be better to go back to using curly braces.

• Wonderful answer!! – Chantola Oct 13 '14 at 2:33

Since factors come in pairs, the largest that the smaller factor can be is the square root of the number. So you can say

// we only need to find the smaller factor, so do an extra multiplication
// to save some of the loop iterations
while ( possibleFactor * possibleFactor < candidate )


Note that I renamed b and x to more descriptive names. As always, comment on anything clever that you do. That way you don't need to be clever to read it later and neither do we.

I'd call PrimeTest IsPrime instead and have it return a boolean (true or false). Then you can call it

if ( IsPrime( candidate ) )


or use the ternary operator as Jamal suggests.

cout << candidate << " is" << (IsPrime( candidate ) ? " " : " NOT ") << "prime.";


I tend to be leery of concatenating strings as they can be hard to localize. Obviously that shouldn't matter for a learning program, but it might be a habit that you want to avoid developing. So there is an argument that using the if is superior to the ternary operator since you are dealing with text output. A quick Google search finds this discussion about best practices for localization in C++. Note that it actually recommends using printf (a C function) over cout (a C++ object).

• what is if (IsPrime(Candidate)) doing? How will this cause a bad habit to me? – Chantola Oct 13 '14 at 2:46
• @Chantola I edited my answer. Hopefully it's clearer now what I'm trying to say. You're comment suggests that you were hearing the opposite of what I intended. – Brythan Oct 13 '14 at 3:00
• I'd add parentheses around the ternary operator in your last code snippet. – user253751 Oct 13 '14 at 9:53

Includes:

You have a lot of #includes for such a tiny program. "stdafx.h" is added by default by Visual Studio. It is useless here, so you should remove it. I think you should be able to configure the IDE so that is doesn't add that by default to every project.

You don't need both <iostream> and <iomanip>. Just iostream will be enough for cin and cout.

<cstdlib> is also not necessary here, since you are not using any of the C library functions.

<cmath> is also not being used. <math.h> is C's version of cmath. You should not have to add it directly to a C++ program.

using namespace std:

Other things:

You should avoid separating a function with prototype and implementation when an inline implementation will do. Move the implementation of PrimeTest() to where its prototype is.

Unusual way of returning a value:

if (x % b == 0)
{
}


Why did you bother assigning a value to Answer to then return it right on the next line? This should be just:

if (x % b == 0)
{
return 0;
}


Same problem with the last return on PrimeTest().

But actually, PrimeTest() should return a bool, so that 0 becomes a false.

IsPrime() would probably be a better name for the function.

• Several wrong answers, first of all, I do need #include "stdafx.h" or it won't run. and using namespace std; is bad practice, but not with such a small program like this. I get it if im building a large program with vast libraries that can intertwine, but not in this simple program. – Chantola Oct 13 '14 at 2:30
• Besides that, it's great information thank you! – Chantola Oct 13 '14 at 2:31
• What kind of errors do you get without stdafx.h? It is just VS clutter as far as I know, but shouldn't be anything that your program really needs. – glampert Oct 13 '14 at 2:32
• @Chantola: That becomes an issue if you create your project with precompiled headers (there should be a checkmark for that). If you leave it cleared, you won't be tied to stdafx.h. – Jamal Oct 13 '14 at 2:36
• I see. Then you would indeed have to disable it on the IDE somewhere. Well, disregard that then. But bare in mind that this is just something imposed by your IDE. There is no requirement that a C++ program has to include stdafx.h. – glampert Oct 13 '14 at 2:37

## Code Review

Stop doing this:

using namespace std;


Why is “using namespace std;” considered bad practice?

That's a really bad variable name:

    int X = 0;
cout << "Enter a number ";
cin >> X;


Variable names should be used to make the code self explanatory.

Here you have a lot of repeated code:

    if (PrimeTest(X) == 1)
{
cout << X << " is prime";
}
else
{

cout << X << " is NOT prime";
}


Simplify with:

    std::cout << "\n\n\n\t\t\t"
<< X << "is "
<< (PrimeTest(X) ? "prime" : "NOT prime"
<< "\n\n\n\t\t\t";


main() is special. You don't need return 0 in main as it will be generated automatically. I use the fact that it is not present to indicate that the application never fails.

    return 0;


This function returns true/false

int PrimeTest(int x)


So you should declare it as returning bool.
Also it would make it clearer that it is a yes/no test by making the function name is<Test>() name. Thus I would have declared it:

bool isPrime(int x);


Review the print statement above now. Does it make it easier to read and understand what is happening when you use the name?

if (isPrime(7)) {std::cout << "prime\n";}


### Algorithm

Your implementation is pretty bog standard (no real optimizations). You could look up a couple of alternative methods and pick a better one.

### Cashing

The result is consistent. So you may as well record the answer for later re-use (so you don't have to re-calculate).

Also when of the better algorithms use all the previous primes (rather than all the numbers). So if you record all the previous primes then calculating this one becomes a lot easier. As you only have to scan from the last known prime forward. As this gets bigger each time you get quicker as the program runs.

You only need to check up to the square root rounded down of the number you are testing. To test 195, test up to 13.

All primes are of the form $6n±1$ except 2 and 3. This prevents useless checking of 4, 6, 8, 10, 12, etc... and 3, 6, 9, 12, etc...

I know there are numbers of the form $6n±1$ that are not prime like 25, so this still can be improved.