2014-09-11

# Problem 003: Largest prime factor

Description:

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

What is the largest prime factor of the number 600851475143 ?

Solution:
89197939490919v          >00g10g1-:10p%#v_10g:30p1-40pv
v+*29191929891<          ^    <         <_v#!  %g04g03<
>*+*+*+*+*+*+*v >"{.i "+**10p#^ #p #0 #0 <>40g:1-40p2-|
>#^ +# *# +# *# +# *# +# *# +#    <@.g03<
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

This problem is the reason why I changed the internals of my interpreter to int64 (because the numbers are too big for int32).

Fortunately the number is still small enough to brute-force the prime factors, going from the biggest factor to the smallest, the first factor (that is also a prime) that my code finds is the solution.

 Interpreter steps: 31 579 516 Execution time (BefunExec): 9.55s (3.31 MHz) Program size: 55 x 4 (fully conform befunge-93) Solution: 6857 Solved at: 2014-09-11

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript