Skip to content

Instantly share code, notes, and snippets.

@TravisL12
Last active December 25, 2015 15:59
Show Gist options
  • Select an option

  • Save TravisL12/7002295 to your computer and use it in GitHub Desktop.

Select an option

Save TravisL12/7002295 to your computer and use it in GitHub Desktop.
Solutions to Project Euler #10 (http://projecteuler.net/problem=10) "Find the sum of all the primes below two million"
def primes(num)
ceiling = num
number_set = 2.upto(ceiling).map(&:to_i)
non_primes = {}
number_set.each do |prime|
next unless non_primes[prime].nil?
number_set.each do |multiple|
next_non_prime = (prime * multiple)
break if next_non_prime > ceiling
non_primes[next_non_prime] = false
end
end
puts (number_set - non_primes.keys).inject(:+).to_s
end
def benchmark
t1 = Time.now
yield
puts "#{Time.now - t1}"
end
num = 2_000_000
benchmark { primes(num) }
def primesTRL(num)
ceiling = num
number_set = 2.upto(ceiling).map(&:to_i)
non_primes = {}
number_set.each do |prime|
next unless non_primes[prime].nil?
max_val = ceiling / prime
break if max_val < prime
prime.upto(max_val) do |multiple|
next_non_prime = (prime * multiple)
non_primes[next_non_prime] = false
end
end
puts (number_set - non_primes.keys).inject(:+).to_s
end
def benchmark
t1 = Time.now
yield
puts "#{Time.now - t1}"
end
num = 2_000_000
benchmark { primesTRL(num) }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment