Thread: Euler's problem #3

http://projecteuler.net/index.php?section=problems&id=3

"The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?"

--

Code:

unsigned long long int y = 600851475143;	// wow thats long

for ( int i = 0; i<(y/2); ++i)
{
	std::cout << "Check " << i << "\n";
}

Just one quick question, I'm already sure this is the wrong approach so I'm researching the right way to do it in C++, but, this has me wondering. Is this a safe-check? That is, will y/2 end up being the exact value (a decimal, compared to an int which I assume it would just drop the 1.5 value to 1?) I would try running it but well it has to loop through 30 million times and my computer isn't that fast

It you check it against all values in that range, you'll find what it is and isn't divisible by, but how does that help you to find the prime factors?

For example, 13195 is also divisible by 35 (5 * 7) but that is not a prime factor. You might need to look for a different approach.

Since this is a challenge you might rather figure it out yourself or seek materials on prime factorization on the internet yourself.

When concerning prime factorization, you might be more interested in the square root of the value, rather than half of it.

Yeah I clearly have the wrong approach going on lol. I didn't have any clue at all on where to start until I did some research, so now I'm working on solving the problem.

But I'm still curious, will i<(y/2) work and give me the number 300xxxxxxxxx.5 which would (I assume) round down instead of up? (Because I assume it would just drop that value, but I dunno...) Also, another thing I just realized an int probably couldn't store that number divided by two so it would probably eventually fail. (I dunno why I thought it would only run 30 million times lol, must have miscounted...though I knew it wasn't in the millions. Maybe I'm just crazy)

Yes, integer division truncates (chops off decimal part).

Also, another thing I just realized an int probably couldn't store that number divided by two so it would probably eventually fail.

That too.

In any case, I did this with Python (where large integers are no problem) and it takes about a blink of an eye to get the answer (with a suitable algorithm - perhaps with a few thousand divisions, rather than millions).