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<int> 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<int>& 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 the cost of making this more complicated, you could change this to
primeCandidate += increment; increment = 6 - increment; }
Where increment would be initialized as
int increment = 2;
And you'd start primeCandidate at 5. You'd also only do one isPrime check per iteration of the while loop.
