Cover by Leonard Richardson, Lucas Carlson

Safari, the world’s most comprehensive technology and business learning platform.

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required

O'Reilly logo

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

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required