Largest prime factor
2014-09-11
Problem 003: Largest prime factor
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<
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 |