Sieve of Eratosthenes

Ruby code posted by Drangon
created at 21 Sep 21:40

Edit | Back
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def sieve_of_eratosthenes(max_prime)
  sieve = Array.new(max_prime, true)
  sieve[0] = sieve[1] = false

  2.upto(Math.sqrt(max_prime)) do |i|
    if sieve[i]
      (i**2).step(max_prime, i) do |j|
        sieve[j] = false
      end
    end
  end

  result = []
  sieve.each_index do |i|
    result << i if sieve[i]
  end

  return result
end
362 Bytes in 4 ms with coderay