Skip to content

Instantly share code, notes, and snippets.

@JamesMcMahon
Last active September 24, 2016 20:44
Show Gist options
  • Save JamesMcMahon/9192a7af8e26f72538d5fc52df9dc714 to your computer and use it in GitHub Desktop.
Save JamesMcMahon/9192a7af8e26f72538d5fc52df9dc714 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes in Ruby
#!/usr/bin/env ruby
def gen_primes(n)
sieve = Array.new(n) { |i| i > 1 }
(0...Math.sqrt(n)).each do |i|
next unless sieve[i]
(i * i...n).step(i) { |j| sieve[j] = false }
end
sieve.map.with_index { |prime, index| index if prime }.compact
# for count
# primes.count { |p| p }
end
print gen_primes(ARGV.first.to_i)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment