Third problem: Largest prime factor

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

What is the largest prime factor of the number 600851475143?

I am partial to a very simple code to find prime numbers… without actually storing any prime numbers anywhere. It goes like this in julia:

function helper(x,n)
  if x==1 
    return n
  elseif x%n==0 
    return helper(x/n,n)
  else 
    return helper(x,n+1)
  end
end

largestprimefactor=x->helper(x,2)

This can then be used to obtain our answer:

julia> largestprimefactor(600851475143)
6857
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: