O'Reilly logo

Ruby Cookbook by Leonard Richardson, Lucas Carlson

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required