C++ For Euler Problem 3 Here's my solution for Euler Problem 3:

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

I'm using the Euler problems to learn some basics of C++. Are there any C++ &quot;conventions&quot; I'm missing, or any languages features I could use to get a better understanding of C++?
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

#include &quot;fibonacci.h&quot;
#include &lt;limits&gt;

int get_prime_above(int i);

bool is_prime(int number);

bool has_decimals(float number);


int main() {

    // What number are we getting the prime factors for?
    long target_number = 600851475143;

    // Holds the prime factors.
    std::vector&lt;int&gt; primes;

    // No point dividing by 1, it's a useless factor in this context.
    int current_prime = get_prime_above(1);
    while (target_number &gt; 1) {
        // Does the target divide by the prime evenly?
        long result = target_number % (long) current_prime;
        if (result != 0) {
            // If not, move on to the next prime.
            current_prime = get_prime_above(current_prime);
            continue;
        }

        // If it does, push the prime
        primes.push_back(current_prime);
        // Change the target number to what ever is left to work out
        target_number = (long) target_number / (long) current_prime;
        // And reset the prime.
        current_prime = get_prime_above(1);
    }

    // Sort and reverse the primes,
    // so the highest will be at index 0
    std::sort(primes.begin(), primes.end());
    std::reverse(primes.begin(), primes.end());

    std::cout &lt;&lt; &quot;Largest prime: &quot; + std::to_string(primes[0]) &lt;&lt; std::endl;
}

/**
 * Get the next prime number above i.
 * @param i
 * @return
 */
int get_prime_above(int i = 1) {
    // Current number we're checking.
    int current_number = 0;
    while (current_number &lt; std::numeric_limits&lt;int&gt;::max()) {

        // If it's lower than what the user wants, just keep incrementing.
        if (current_number &lt;= i) {
            current_number++;
            continue;
        }

        // If it's prime, return it.
        if (is_prime(current_number)) {
            return current_number;
        }

        current_number++;
    }
    throw std::runtime_error(&quot;Couldn't find a prime within the int maximum value&quot;);
}

/**
 * Is the given number a prime?
 * @param number
 * @return bool
 */
bool is_prime(int number) {
    // Loop all the numbers between (not inclusive of) 1 and number
    // as we know that 1 and number will always have no decimal.
    // If number is 7, it would loop 2..6
    for (int tmp = number - 1; tmp &gt; 1; tmp--) {
        // Divide the number
        float result = ((float) number / (float) tmp);

        // If the result has decimals, it doesn't divide equally
        // so return false.
        if (!has_decimals(result)) {
            return false;
        }
    }

    // All the in between numbers had decimals, so it's a prime.
    return true;
}

/**
 * Is this number a decimal?
 * If converting the float to an int and back again changes the value,
 * then the int conversion removed some decimals.
 * @param number
 * @return bool
 */
bool has_decimals(float number) {
    return number != (float) (int) number;
}
I tried this in VS2019 and I needed to #include &lt;string&gt; in order to compile. 

Then I get a warning for the line 


long product_of_primes = 600851475143;



which says


  truncation from __int64 to long


which means that long is not enough to hold that number. Since it's positive, I changed that to unsigned long long.

For the remaining review, I'll go through your code from top to bottom, trying to understand it. Whenever I find something, I'll point it out.



If you change


  // Holds the prime factors.
  std::vector&lt;int&gt; primes;



to

std::vector&lt;int&gt; prime_factors;


you can get rid of the comment and the variable becomes self-explaining.



The method


int get_prime_above(int i = 1)



IMHO should not support a default value. As you see in your code, you're calling it with


int current_prime = get_prime_above(1);



and seeing a call with the default value

int current_prime = get_prime_above();


would not make sense to the reader.

Another open question is: which prime above i will the method return? Just any? The next? At this point of understanding and from the comment, I'd propose the name

next_prime_after(int i)


At the same time, I'd change the parameter i to minimum.



I stumbled over the line


while (target_number &gt; 1) {



because I was expecting some other number increasing towards that target. However, your code reduces target_number to become 1. Given that target_number is a product of prime numbers, I would call it product_of_primes instead. Again, you can now remove the comment for that variable.



Again, you need a comment to explain what a variable means:


// Does the target divide by the prime evenly?
long result = product_of_primes % (long)current_prime;



Note that the comment asks a yes/no question, which is why I would expect a boolean. However, the result is a long. Also, the cast to (long) seems redundant. My proposal:

bool is_divisor = 0 == product_of_primes % current_prime;


This also changes the conditional statement to

if (!is_divisor) {


so the comment here is redundant, so it can be removed:

// If not, move on to the next prime.
current_prime = next_prime_after(current_prime);




In order to simplify the branch we have now:

if (!is_divisor) {
    current_prime = next_prime_after(current_prime);
    continue;
}


you can initialize current_prime to 1 and then call next_prime_after() at the beginning of the loop like this:

int current_prime = 1;
while (product_of_primes &gt; 1) {
    current_prime = next_prime_after(current_prime);
    bool is_divisor = 0 == product_of_primes % current_prime;
    if (!is_divisor) continue;
    ...
    current_prime = 1





product_of_primes = (long)product_of_primes / (long)current_prime;



This IMHO has redundant casts and can be simplified to

product_of_primes = product_of_primes / current_prime;



   This, however, will change the result from 71 to the correct value expected by Project Euler to complete the challenge.





current_prime = 1;



IMHO, you don't need to restart at the beginning, since you'll not find prime factors lower than the one you already found.

However, it will not change performance significantly.



Instead of reversing


std::reverse(prime_factors.begin(), prime_factors.end());



you can simply get the last element of the vector

std::cout &lt;&lt; "Largest prime: " + std::to_string(prime_factors.back()) &lt;&lt; std::endl;


or (my preferred option in this case) sort in descending order

std::sort(prime_factors.begin(), prime_factors.end(), std::greater&lt;int&gt;());


---- Dunno, the horizonal rulers stop working in this line

Woah, this is ugly:


if (current_number &lt;= minimum) {
  current_number++;
  continue;



This can simply be replaced by

int current_number = minimum + 1;


And in consequence the loop can be re-written as

int next_prime_after(int minimum) {
    int current_number = minimum + 1;
    while (!is_prime(current_number)) {
        current_number++;
    }
    return current_number;
}




In that same method, we probably get a performance benefit of a factor of 2 if you move to odd numbers. 

int next_prime_after(int minimum) {
    int current_number = minimum + 1;
    current_number += minimum % 2; // ensure odd number
    while (!is_prime(current_number)) {
        current_number += 2;
    }
    return current_number;
}




A had a WTF moment here:


float result = ((float)number / (float)tmp);
// If the result has decimals, it doesn't divide equally
// so return false.
if (!has_decimals(result)) {



Why? Because you already did a proper divisability check somewhere else (cited from the original code):


// Does the target divide by the prime evenly?
long result = target_number % (long) current_prime;



That way, you can get rid of the whole method has_decimals().




for (int tmp = number - 1; tmp &gt; 1; tmp--) {



When you learned dividing numbers in school, did you start by dividing an arbiotrary number like 56 by it's predecessor 55 to check if it is a prime factor? Certainly not. So let's not do it in your code as well. Go simple: check if 56 is divisable by 2.

Oh, and BTW: if you can't divide 56 by 2, you can also not divide it by anything > 28, right? Make a huge performance impact of a factor ~10.

bool is_prime(int number) {
    for (int divisor = 2; divisor &lt; number/2; divisor++) {
        bool is_divisor = 0 == number % divisor;
        if (is_divisor) {
            return false;
        }
    }
    return true;
}


This could be reduced to sqrt(2) instead of number/2 if you think about it.

Starting at 3 and testing odd numbers only will increase by another factor of 2:

bool is_prime(int number) {
    if (number % 2 == 0) return false;
    for (int divisor = 3; divisor &lt; number/2; divisor+=2) {
        bool is_divisor = 0 == number % divisor;
        if (is_divisor) {
            return false;
        }
    }
    return true;
}




For this Project Euler question, int prime factors see to be good enough. For general purpose factorization, you should consider at least long.



My final proposal for you

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
#include &lt;string&gt;
#include "fibonacci.h"
#include &lt;limits&gt;

int next_prime_after(long minimum);
bool is_prime(long number);

int main() {

    unsigned long long product_of_primes = 600851475143;
    std::vector&lt;int&gt; prime_factors;

    int current_prime = 1;
    while (product_of_primes &gt; 1) {
        current_prime = next_prime_after(current_prime);
        bool is_divisor = 0 == product_of_primes % current_prime;
        if (!is_divisor) continue;

        prime_factors.push_back(current_prime);
        product_of_primes = product_of_primes / current_prime;
        current_prime--;
    }

    std::sort(prime_factors.begin(), prime_factors.end(), std::greater&lt;int&gt;());
    std::cout &lt;&lt; "Largest prime: " + std::to_string(prime_factors[0]) &lt;&lt; std::endl;
}

/**
 * Get the next prime number above minimum.
 * @param minimum
 * @return
 */
int next_prime_after(long minimum) {
    long current_number = minimum + 1;
    current_number += minimum % 2; // ensure odd number
    while (!is_prime(current_number)) {
        current_number += 2;
    }
    return current_number;
}

/**
 * Is the given number a prime?
 * @param number
 * @return bool
 */
bool is_prime(long number) {
    if (number % 2 == 0) return false;
    for (long divisor = 3; divisor &lt; number/2; divisor+=2) {
        bool is_divisor = 0 == number % divisor;
        if (is_divisor) {
            return false;
        }
    }
    return true;
}


Summary

I hope you agree with my proposals and see that the resulting code is


easier to read
bug fixed
faster by a factor of ~100 (measured using QueryPerformanceCounter())