Why this code doesnt work? exercise: What is the largest prime factor of the number 600851475143 ?

Question

I used cin >> max to test for different answers because the number in exercise was taking too long to calculate

#include <iostream>
using namespace std;

int main()
{
bool isPrime = true;
long long res = 0;
long long max = 600851475143;
cin >> max;
for (long long x = 1; x < max; ++x)
{
if (max % x == 0)
{
for (long long int i = 2; i <= x / 2; ++i)
{
if (x % i == 0)
{
isPrime = false;
break;
}
}
if (x > res && isPrime == true)
{
res = x;
}
}
}
cout << res;
}

Answer 1

The cause for that taking so long is the 600 billion iterations you're going through in that loop.

A very effective and simple optimization would be to observe that a factor can't be larger than the number's square root. Iterating up to and including the int at or rounded up from sqrt(max) is all you need. This will cut your iterations down to a square root of 600 billion which should complete far faster.

You might be interested to learn about time complexity. It helps you analyze algorithms to see how quickly they execute, and how they can be optimized.
https://en.wikipedia.org/wiki/Time_complexity

Answer 2

EDIT: This answer is incorrect!! I'm keeping this here just for a reference of comparison.

ItzNekS, here is an implementation of my suggestion:

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
bool isPrime = true;
long long res = 0;
long long max = 600851475143;
long long maxX = (long long)sqrt(max) + 1;
cout << "maxX = " << maxX << endl;
for (long long x = maxX; x >= 1; x--)
{
if (max % x == 0)
{
isPrime = true;
long long int maxI = (long long int)sqrt(x) + 1;
for (long long int i = 2; i <= maxI; ++i)
{
if (x % i == 0)
{
isPrime = false;
break;
}
}
if (x > res && isPrime == true)
{
res = x;
}
}
}
cout << res;
}

That outputs 6857 which matches the answer from the calculator at: https://www.calculatorsoup.com/calculators/math/prime-factors.php

Answer 3

I just learned that my earlier optimization was incorrect. It gives the correct result for the constant number you specified but it would be incorrect if max=14 where the largest prime factor would be 7 for example.

This is based on an answer at:
https://math.stackexchange.com/questions/63276/is-a-prime-factor-of-a-number-always-less-than-its-square-root#:~:text=8%20Answers&text=No.,greater%20than%20its%20square%20root.

Checking if a given integer is prime can be done safely by iterating over 2..sqrt(the number) but the prime factor loop needs to be optimized differently.

Here is a corrected implementation that will work for cases like max=14.

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(long long n)
{
long long int maxI = (long long int)sqrt(n);
for (long long int i = 2; i <= maxI; ++i)
{
if (n % i == 0)
{
return false;
}
}
return true;
}

int main()
{
long long res = 0;
long long max = 600851475143;
long long maxX = (long long)sqrt(max) ;
cout << "maxX = " << maxX << endl;
for (long long x = 2; x <= maxX; x++)
{
if (max % x == 0)
{
if (x > res && isPrime(x))
{
res = x;
}
if (max / x > res && isPrime(max / x))
res = max / x;
}
}
cout << res;
}

Answer 4

thx for the answer, but for any number the code doesnt work, it doesnt do what it should (calculate the largest prime factor)

Answer 5

thank you very much