Greatest program to find the largest prime factor

I was asked this question by project euler -

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

I think I came with the greatest solution in the world.
I challenge anyone to do better than this.
It's 10 lines of code and finds the solution in less than 10 milliseconds.

Seriously, you can try as much as you want, but this solution is already the best in the world.

#include <stdio.h>
int main(void)
{
int i = 2;
long n = 600851475143;
for (; n > 1; i++)
for (; n % i == 0; n /= i)
printf("%d\n", i);
return 0;
}

>>2
Don't run this. It deleted all my Toohoo pictures.

>>2
This brings us to the big question -
Does ReactOS run 2-hu games already?

>>2
This program prints numbers, it doesn't touch your files.
Toohoo pictures are sacred and are not deleted.
The answer is 6857.
There's no better program in the world to achieve this.
ENJOY!

ToeHoe

I ran it in praxis:

do
local i = 2
local n = 600851475143
while n > 1 do
while n%i == 0 do
print2(i)
n = n / i
end
i = i + 1
end
end

71
839
1471
6857

It's a simple and naive solution, running in O(GreatestPrimeFactor(n)) time, i.e. O(n) for primes.
Test it on 60129542116 instead. It's about the size of your test case.
There are better algorithms to solve this problem.

>>6
Why are you lying?

>>7
Too weak to sit up.

>>6
Tested for your number and it still gave me the answer in less than 10 milliseconds.
real 0m 0.00s
You say there's a better algorithm for this¿ Then show it!

What's >>1-san algorithm?
I tried a straight-forward solution of finding a divisor of the number and then checking if it's a prime (using the fact you only need to check the sqrt of it) from the top to bottom, so it eventually shows the largest prime factor of the number (6857) and then finishes.

It takes 0.81 s to complete. so it's at least 80 times slower than >>1-sama's solution.
Can someone explain his program?

>>5
Nice! It's been a long time I played with praxis. It was a bit bloated for me, but had some nice ideas and gave me some fun.

print 6857

>>10
the code is like 3 lines. can't you really understand it?

you suck bro.

I can understand what it does, but I can't understand how it yields in the prime factors of the input number.

>>1
Dear OP, first of all you are measuring the performance of process startup and, to a lesser extent, the write() syscall. You could've noticed it if you inserted a loop in your program and made it store solutions instead of printing, and discovered that you have to repeat it about 1000 times before you get noticeable delay.

You could also figure it from the general principles, that no way performing about 7000 divisions should take 10ms, that's 1428ns per loop iteration, you are clearly about two orders of magnitude off.

Anyway, per my own experiments your code runs in about 0.25ms/loop (full solution), not checking odd numbers predictably speeds it up twofold, modifying it as follows speeds it up fivefold on top of that.

for(long limit = sqrt(n) + 1; i < limit; i += 2)
for (;n % i == 0; n /= i, limit = sqrt(n) + 1)
solutions.insert(i);
solutions.insert(n);

>>13
as you divide n by each prime factor, the next prime factor becomes the smallest number that will divide n thus by the end you will be left with the largest prime factor.

Thanks. I understand it now.

Wheel factorization, bitch.

project euler

Go to some real programming problem solving site like acm.timus.ru for example.

>>18
Thanks for the link. Russian programmers must be awesome if they routinely solve problems at this level.

>>18
What did you do to Nikita, motherfucker!?

printf("6857\n");

_ _
>(')____, >(')____,
(` =~~/ (` =~~/
~^~^`---'~^~^~^`---'~^

>>19

Check the top authors, they solve N=NP questions like breakfast.

Anyway, it's a great site to polish your programming skill with those low tier problems.