Michael Cordell's Blog

Prime Factor Problem Cheat Sheets

20 Dec 2014

1 is not a prime number.

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Wikipedia

Finding Prime Numbers

Sieve of Eratosthenes

A basic implementation of the sieve of Eratoshenes I wrote:

def primes(max_value)
  search_space = Array.new(max_value, true)
  prime_range = (2..max_value)

  prime_range.each do |i|
    if search_space[i]
       j = 2 * i
       while j <= max_value
          search_space[j] = false
          j += i
       end
    end
  end

  prime_range.map{ |i| i if search_space[i] }.compact
end
comments powered by Disqus