You want to generate a sequence of prime numbers, or find all prime numbers below a certain threshold.

Instantiate the `Prime`

class
to create a prime number generator. Call `Prime#succ`

to get the next prime number in
the sequence.

require 'mathn' primes = Prime.new primes.succ # => 2 primes.succ # => 3

Use `Prime#each`

to iterate
over the prime numbers:

primes.each { |x| puts x; break if x > 15; } # 5 # 7 # 11 # 13 # 17 primes.succ # => 19

Because prime numbers are both mathematically interesting and useful in cryptographic applications, a lot of study has been lavished on them. Many algorithms have been devised for generating prime numbers and determining whether a number is prime. The code in this recipe walks a line between efficiency and ease of implementation.

The best-known prime number algorithm is the Sieve of Eratosthenes, which finds all primes in a certain range by iterating over that range multiple times. On the first pass, it eliminates every even number greater than 2, on the second pass every third number after 3, on the third pass every fifth number after 5, and so on. This implementation of the Sieve is based on a sample program packaged with the Ruby distribution:

def sieve(max=100) sieve = [] (2..max).each { |i| sieve[i] = i } (2..Math.sqrt(max)).each do |i| (i*i).step(max, i) { |j| sieve[j] = nil } if sieve[i] end sieve.compact end sieve(10) # => [2, 3, 5, 7] sieve(100000).size # => 9592

The Sieve is a fast ...

Start Free Trial

No credit card required