Project Euler Problem 3

[edge6768]

Hi all,

Recently trying to get back into programming and figured going through the Project Euler problems would be a good way to do so. However, I'm stuck on number 3....

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

#include <iostream>

using std::cout;

#define VAL 600851475143

typedef unsigned int uint;

bool isPrime(uint toCheck);

int main(int argc, char** argv) {
	uint temp = VAL / 2;
	for(; temp > 0; temp--) {
		if(VAL % temp == 0 && isPrime(temp)) {
			cout << temp << '\n';
			return 0;
		}
	}
return 0;
}

bool isPrime(uint toCheck) {
	uint temp = toCheck / 2;
	if(temp % 2 == 0) return false;
	if(temp % 5 == 0) return false;
	for(uint i = toCheck / 2; i > 2; i -= 2) {
		if(toCheck % i == 0) return false;
	}
return true;
}

I used preprocessor macros for VAL as I figured it would overflow even on a long long int. Still the search space is massive - what might be a more elegant approach?

Edit: I am somewhat familiar with Python as well - would it be a better option for something like this?

[Ganado]

I am somewhat familiar with Python as well - would it be a better option for something like this?

That's opinion-based, but Python does handle "big integers" (integers beyond 64 bits) automatically for you.

You can get it to work in C++ as well, but I just consider it useless boilerplate, and the actual fun part is solving the mathematics.

But if you want to do in in C++, you need to implement what are known as "Big Integers". Integers that can handle arbitrarily large numbers. It's usually implemented with some sort of array of numbers, to glue the digits of a large number together, and the algorithm to add/multiply two big integers can be similar to what you probably learned in elementary/grade school (e.g. look at first digit, then "carry the 1" (the overflow) to the next highest digit).
You can see an implementation here: https://github.com/panks/BigInteger which you can download and add to your project.

Also, avoid macros in modern C++. Prefer const or constexpr.

e.g.
const unsigned int Val = 5738383u;

[dutch]

A long long is 64 bits, so it will not overflow.
The maximum value in an unsigned long long is
2**64 - 1 = 18446744073709551615 (where ** is exponentiation)

Don't call all your variables "temp". Every variable is ultimately temporary, so it's a name of last resort. Even "num" is better than temp.

And you only need to test divisors up to (and including) the square root.

#include <iostream>
#include <cmath>

using ull = unsigned long long;

const ull Value = 600851475143;

bool isPrime(ull num) {
    if (num <= 2) return num == 2;
    if (num % 2 == 0) return false;
    ull limit = std::sqrt(num);
    for (ull i = 3; i <= limit; i += 2)
        if (num % i == 0)
            return false;
    return true;
}

int main() {
    ull divis = std::sqrt(Value);
    if (divis % 2 == 0) --divis; // ensure it's odd
    for ( ; divis >= 3; divis -= 2)
        if (Value % divis == 0 && isPrime(divis))
            break;
    std::cout << divis << '\n';
}

[Ganado]

Oh, whoops, my bad. The early problems can fit into 64-bits. Although, I believe other Euler problems that OP will encounter in the future will overflow, unless handled as strings/BigInts.

[dutch]

My implementation is incorrect in the general case even though it happens to work for the given input value.

Although to test if a number is prime you only need to test up and including the square root, to find the highest prime factor of a number you need to test above that, right up to the number since it may itself be prime. For very large primes the trial-division approach becomes infeasible.

Also, the sqrt should be done using a long double since a regular double only has 53 bits of precision so it may underestimate the sqrt of a 64 bit value.

[dhayden]

The Project Euler problems are all looking for clever solutions. In this case, the fastest way to find the largest prime factor is to start by peeling off smaller factors.

A word of advice: save your code. Lots of PE problems require finding prime factors or prime numbers. I eventually ended up with a class that finds them quickly.

Edit: I just found me solution. You definitely want to start with the small factors. My simple minded solution runs in 11ms on a crappy old Sparc computer.

[dutch]

I assume you mean "solution" to the given input. Mine solves the given input, too. But in general, peeling off the small factors won't work. What if the value is just as large as the given one but is prime itself? What if the value is 5 orders of magnitude larger and prime? If all we need is to solve the given input, then this is the best answer:

#include <iostream>
int main() { std::cout << 6857 << '\n'; }

[ne555]

> Although to test if a number is prime you only need to test up and including
> the square root, to find the highest prime factor of a number you need to
> test above that, right up to the number since it may itself be prime.
if you didn't find a prime divisor till the square root, the number is prime (the smallest divisor can't be bigger than its square root)
once you find a divisor, you may remove it from the number, that way you never need to test above sqrt(n)

[jonnin]

you can find the 71 factor almost instantly via

cout << __gcd(600851475143ull,2943621299625756750ull)<< endl;
cout << __gcd(600851475143ull,1000259879166048557ull)<< endl;
cout << __gcd(600851475143ull,2677191508194702433ull)<<endl;

which gets you anything up to & including 131. (you would have to iterate these until all 3 came back with 1s if you want all the factors).

which is about useless if the end-game is looking for bigprime*bigprime factorization, the golden problem..

[dutch]

@ne555, You're absolutely right. I don't know what I was thinking there. :-(

[dhayden]

But in general, peeling off the small factors won't work.

Sure it will. The idea is just to find all prime factors of the number and select the largest one. Here's my program's output:

600851475143 / 71 = 8462696833
8462696833 / 839 = 10086647
10086647 / 1471 = 6857
answer is 6857
903 microseconds

Each time you find a factor the search space gets reduced. In the end, I count up from 3 to 1471. That's better than counting down from 775,146 (sqrt(600851475143)) to 6,857.

[dutch]

@dhayden, You're right. I wasn't thinking.

[jonnin]

I count up from 3 to 1471.

and then you have to check 6857 to see if its prime (it is) and then stop. that last check is probably costing a good bit of your time at a guess (?).
using a pre-generated list of primes I had to do 903 checks all told. Not sure if this matches yours or not.

[dhayden]

and then you have to check 6857 to see if its prime

Actually you don't. Since you've already eliminated factors through 1471 and 1471>sqrt(6857), you know that 6857 is prime.

[jonnin]

well duh, of course :)