6
\$\begingroup\$

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()
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Ah you're right. If there aren't any factors before sqrt(n), then there aren't any after either. Thanks for your answer! \$\endgroup\$ – Gandhichainz Jul 6 '15 at 2:31
  • \$\begingroup\$ Also, there are 6 kind of numbers, those ~0, ~1, ~2, ~3, ~4 and ~5 (on modulo 6). ~0, ~2, ~4 are divisible by 2, ~3 are divisible by 3, so you only need to test those ~1 and ~5 (but remember to test 2 and 3 before looping, loop becomes a +2 followed by a +4 step). \$\endgroup\$ – Dietr1ch Jul 6 '15 at 3:07
  • \$\begingroup\$ Very interesting. I'll be sure to take an even more mathematical approach from now on. \$\endgroup\$ – Gandhichainz Jul 6 '15 at 20:19
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Why do we not include numbers that aren't adjacent to multiples of 6 but are still odd? Is it because numbers that aren't so are definitely not prime? \$\endgroup\$ – Gandhichainz Jul 6 '15 at 20:20
  • \$\begingroup\$ @Gandhichainz: Because those are divisible by 3, and you already check 3 at the beginning of the algorithm. \$\endgroup\$ – barak manos Jul 6 '15 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.