Project Euler #3

Question

I wrote some code to solve this question and I was wondering if it was efficient or not.

I just started learning code last week and I would like to get some input so I can get in the habit of writing the most efficient code possible.

#include <iostream>
using namespace std;


// What is the largest prime factor of the number 600851475143?
int main()
{
    long long greaterFactor = 600851475143;
    bool factorIsPrime = true;

    for (long long i = 3; i <= greaterFactor; i += 2)
    {
        if (greaterFactor % i == 0)                 // checks if i is a factor
        {
            if (greaterFactor / i >= i)             // if the other factor (not i) of greaterFactor is greater or equal (for squared numbers)
            {
                greaterFactor /= i;                 // greaterFactor becomes the other factor
                i -= 2;                             // in case prime factor shows up more than 1 time (eg - > 11 * 11 * 17 -> 11 & 11 * 17 -> 11 & 11 & 17
            }                                       // then continues to check next integers to completely factor smaller factors until greaterFactor has no more factors
        }
    }

    cout << "The largest prime factor of the number 600851475143 is:\n" << greaterFactor << endl;
    return 0;
}   // end main()

Answer 1

It's not currently (or at least publicly) known how to factor numbers quick, but it's easy to check if the factors really give the number back (just multiply them).

That problem is at the core of RSA cryptography and other similar cryptography schemes.

So you are not likely to find a much faster algorithm than brute force, you may improve the bounds (are there divisors past \$\sqrt{n}\$?) and also skip numbers that you can predict that wont divide \$n\$, but it's hard to do much better without making yourself rich or famous.

Answer 2

You may divide the input number by only 2, 3, and all the numbers that are adjacent to multiples of 6.

In addition to that, if you haven't found any prime factor up to the square-root of the input number, then you may return the input number itself as the greatest prime factor, since this number is prime.

uint64_t GetGreatestFactor(uint64_t inputNumber)
{
    while (inputNumber % 2 == 0)
        inputNumber /= 2;
    if (inputNumber == 1)
        return 2;

    while (inputNumber % 3 == 0)
        inputNumber /= 3;
    if (inputNumber == 1)
        return 3;

    uint64_t limit = static_cast<uint64_t>(sqrt(inputNumber));

    for (uint64_t i = 5, j = 2; i <= limit; i += j, j = 4-j)
    {
        while (inputNumber % i == 0)
            inputNumber /= i;
        if (inputNumber == 1)
            return i;
    }

    return inputNumber;
}