sieve.rb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Sieve
  def initialize(limit)
    @limit = limit
  end

  def primes
    # Start with some "special cases":
    # 0 included for convenience and is not prime
    # 1 is not prime
    # 2 is prime but special case as it's the only even prime
    # Then mark even numbers as non-prime and assume odd numbers are prime.
    is_prime = [false, false, true][0..@limit] + (3..@limit).map(&:odd?)
    limit_sqrt = (@limit**0.5).to_i + 1

    (3..limit_sqrt).step(2) do |i|
      if is_prime[i]
        # Found the next prime... mark all its multiples as non-prime
        # (not including itself)
        (i * i..@limit).step(i) do |j|
          is_prime[j] = false
        end
      end
    end

    (2..@limit).select { |i| is_prime[i] }
  end
end

@remcopeereboom thinks this looks great

Comments

Improved the last line.

Also ran it through Rubocop which had the helpful suggestion of using odd? on line 12.

helenst commented 16 March 2016 at 09:12 UTC

You're not logged in right now. Please login via GitHub to comment