Skip to content

Instantly share code, notes, and snippets.

@pgburt
Created November 20, 2015 23:29
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save pgburt/7ca73eadaca00717b62f to your computer and use it in GitHub Desktop.
# https://projecteuler.net/problem=3
# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?
sleep(5)
$factor_this = 600851475143.0
$primes = [2, 3]
$solution = [0]
def add_to_primes
succeed = false
target = $primes.last
begin
target += 1
$primes.each do |x|
break if (target % x) == 0.0
succeed = true if x == $primes.last
end
end until (succeed)
# puts "pushing #{target}"
$primes.push(target)
end
# Calculate all the primes we'll need
(0..9999).each do |x|
add_to_primes
end
# Find the primes that factor cleanly
$primes.each do |x|
puts "Trying #{x}"
if ($factor_this % x == 0.0)
$factor_this = $factor_this / x
puts "#{$factor_this * x} / #{x}"
$solution.push(x)
if $solution.include? $factor_this
break
else
redo
end
end
end
puts "The solution is #{$solution}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment