Project Euler with Befunge


Fork me on GitHub
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