Project Euler # 7 in C++

I attempted the Project Euler question #7 in C++ ("What is the 10 001st prime number?").

I took into account what I've been told about primes in order to create the most efficient algorithm I could in order to solve this. I would like to know if there is anything else I can do to check even fewer numbers for an even more efficient algorithm.

Also, I'm wondering if creating and using functions would be good practice in this scenario, and how I could go using functions more in coding.

```
#include
#include

using namespace std;

// What is the 10 001st prime number?
int main()
{
int countPrimes = 2;
int checkIfPrime = 6; // multiples of 6

// sees if numbers adjacent to 6 are prime
bool lessOnePrime = true;
bool plusOnePrime = true;

vector primeVector; // for holding primes to check for future primes
//account for primes 2 and 3 beforehand:
primeVector.push_back(2);
primeVector.push_back(3);

while (countPrimes < 10001) // checks until the 10001st prime has been found
{
for (int i = 0; primeVector[i] <= sqrt(checkIfPrime + 1); i++) //checks only prime factors up to the square root
{
// checks if numbers adjacent to 6 have prime factors
// if so, makes their respective booleans false
if ((checkIfPrime - 1) % primeVector[i] == 0)
{
lessOnePrime = false;
}
if ((checkIfPrime + 1) % primeVector[i] == 0)
{
plusOnePrime = false;
}
// if both adjacent numbers to multiples of 6 aren't prime, exits loop
if (lessOnePrime == false && plusOnePrime == false)
{
break;
}
}

if (lessOnePrime)
{
primeVector.push_back(checkIfPrime - 1);
countPrimes++;
// cout << "#" << primeVector.size() << " prime number:\t" << checkIfPrime - 1 << endl;

I would like to know if there is anything else I can do to check even fewer numbers for an even more efficient algorithm.

The general recommendation is to use a


sieve for this. The one that comes to mind is the Sieve of Eratosthenes.

That said, there are some other comments that I can make on the code as it stands.

int checkIfPrime = 6;       // multiples of 6

Often, your code will read more naturally if you give variables noun names. This tells what you should do with the variable. I'd prefer a name like primeCandidate which describes what it is. Or should be, since 6 isn't actually a number that you want to check.

int primeCandidate = 7;

It can save calculations if you start with 7 rather than 6. Rather than saying primeCandidate-1 and primeCandidate+1, you can just say primeCandidate-2 and primeCandidate. Note that you need the larger number slightly more often.

bool lessOnePrime = true;
    bool plusOnePrime = true;

Since you don't use these outside the while loop nor across iterations, you should define these inside the loop instead. Of course, as we'll discuss later, these aren't actually necessary.

vector primeVector;

This is called Hungarian notation, where you put the type in the name. This can cause difficulty in changing code later. For example, what if you wanted to change from std::vector to a type called List? Should you rename this variable as well? A better name might be primes which works regardless of type.

while (countPrimes < 10001)                 // checks until the 10001st prime has been found

You don't have to track a counter manually. You can just say

while (primes.size() < 10001)

The type already maintains a count for you. You might as well use it rather than duplicate it manually.

for (int i = 0; primeVector[i] <= sqrt(checkIfPrime + 1); i++)      //checks only prime factors up to the square root

You don't need to start at 0 each time. By starting with 5 and 7 and always incrementing by 6, you ensure that it will never be divisible by 2 or 3. So you can skip the first two elements in the vector.

for (int i = 2, n = sqrt(primeCandidate); primes[i] <= n; i++)

You don't need to calculate the square root on each iteration. You can do it once at the beginning of the loop.

You don't need to comment saying that you are only checking to the square root. The code says this. You might want to comment on why it is safe to only check up to the square root.

{
            if ((checkIfPrime - 1) % primeVector[i] == 0)
            {
                lessOnePrime = false;
            }
            if ((checkIfPrime + 1) % primeVector[i] == 0)
            {
                plusOnePrime = false;
            }

            if (lessOnePrime == false && plusOnePrime == false)
            {
                break;
            }
        }

        if (lessOnePrime)
        {
            primeVector.push_back(checkIfPrime - 1);
            countPrimes++;
            // cout << "#" << primeVector.size() << " prime number:\t" << checkIfPrime - 1 << endl;
        }
        if (plusOnePrime)
        {
            primeVector.push_back(checkIfPrime + 1);
            countPrimes++;
            // cout << "#" << primeVector.size() << " prime number:\t" << checkIfPrime + 1 << endl;
        }
        lessOnePrime = true;
        plusOnePrime = true;

This is more complicated than it needs to be. It would be much simpler to use two function calls instead of this for loop.

if (isPrime(primeCandidate - 2, primes))
        {
            primes.push_back(primeCandidate - 2);
        }

        if (isPrime(primeCandidate, primes))
        {
            primes.push_back(primeCandidate);
        }

Yes, this repeats the for loop, but it saves you the internal scaffolding. It also means that if one is a prime and the other isn't, it doesn't keep trying to divide the non-prime one by each potential factor. That loop can exit early. You'd have to profile to be sure, but I'd expect this to be faster.

The function would look something like

bool isPrime(const int candidate, const std::vector& primes)
{
    for (int i = 2, n = sqrt(candidate); primes[i] <= n; i++)
    {
        if (candidate % primes[i] == 0)
        {
            return false;
        }
    }

    return true;
}

I haven't tried to compile it though.

Note that it might be more efficient to use an iterator rather than an index variable. The notation would be more complicated in this case though.

I'll leave writing the actual function to you. Note that even with the overhead of writing the function, you'll still likely shorten the code a bit. You do a lot of effort just to make the single for loop work.

checkIfPrime += 6;
    }

The only change I'd make to this is the variable name. Although if you wanted to simplify the code in the loop at

StackExchange Code Review Q#96414, answer score: 9