You are previewing Ruby Cookbook.

# 2.16. Generating Prime Numbers

## Problem

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

## Solution

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```

## Discussion

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 ...