Euler problem, prime factorization

euler-primes.rb

# find primes up to n
def sieve(n)
  return n if n == 2
  s = (3..n).step(2).to_a
  s.each { |i| s.reject! { |j| j != i && j % i == 0 } }
end

def new_sieve(n)
  (s = maybe_primes(n)).each { |i| s.reject! { |j| j != i && j % i == 0 } }
end

# find largest prime factor
# too slow for big numbers.
def lpf_slow(n)
  sieve(n).reverse.find { |i| n % i == 0 }
end

def max(x,y); x > y ? x : y end

# better lpf - keep dividing out the smallest factor (which is always prime)
# and remember the largest.  returns n if n is prime.
def lpf(n)
  f = (2..Math.sqrt(n)).find { |i| (i==2 || i.odd?) && n % i == 0 }
  f.nil? ? n : max(f, lpf(n/f))
end


# kind of naive way
# optimizations: only check up to sqrt(n), only check odd numbers
# Also all primes except 2 and 3 are of the form 6k +- 1
# So you can check 2 and 3 and then all numbers 6k +- 1 <= sqrt(n)
def maybe_primes(n)
  [2,3] + (1..((n-1)/6)).map { |i| x=6*i; [x-1, x+1] }.flatten
end

def slow_prime?(n)
  true if maybe_primes(Math.sqrt(n)).inject(true) { |r, m| r && (n % m != 0) }
end

def prime?(n)
  lpf(n) == n
end

=begin
s = new_sieve 120_000
puts "sieve 120_000: #{s.length} primes"
puts "first 10: #{s[0..10].inspect}"
puts "last 10: #{s[-10..-1].inspect}"
puts "10001st prime: #{s[10000]}"
=end

=begin
puts "lpf 14 is #{lpf 14}"
puts "lpf 13195 is #{lpf 13195}"
n = 600851475143 
puts "lpf #{n} is #{lpf n}"
puts "#{n} prime? #{prime?(n) ? 'ya' : 'no' }"
puts "#{n} prime (slow)? #{slow_prime?(n) ? 'ya' : 'no' }"
=end

s = new_sieve(2_000_000)
sum = s.inject(0){ |sum, p| sum + p }
puts "sum of all primes below 2 million: #{sum}"