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 way to find the primes smaller than a certain number, but it's memory-inefficient and it's not suitable for generating an infinite sequence of prime numbers. It's also not very compatible with the Ruby idiom of generator methods. This is where the `Prime` class comes in.

A `Prime` object stores the current state of one iteration over the set of primes. It contains all information necessary to calculate the next prime number in the sequence. `Prime#each` repeatedly calls `Prime#succ` and `yield`s it up to whatever code block was passed in.

Ruby 1.9 has an efficient implementation of `Prime#each`, but Ruby 1.8 has a very slow implementation. The following code is based on the 1.9 implementation, and it illustrates many of the simple tricks that drastically speed up algorithms that find or use primes. You can use this code, or just paste the code from Ruby 1.9's `mathn.rb` into your 1.8 program.

The first trick is to share a single list of primes between all `Prime` objects by making it a class variable. This makes it much faster to iterate over multiple `Prime` instances, but it also uses more memory because the list of primes will never be garbage-collected.

We initialize the list with the first few prime numbers. This helps early performance a little bit, but it's mainly to get rid of edge cases. The class variable `@@check_next` tracks the next number we think might be prime.

require 'mathn' class Prime @@primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101] @@check_next = 103 end

A number is prime if it has no factors: more precisely, if it has no prime factors between 2 and its square root. This code uses the list of prime numbers not only as a cache, but as a data structure to help find larger prime numbers. Instead of checking all the possible factors of a number, we only need to check some of the prime factors.

To avoid calculating square roots, we have `@@limit` track the largest prime number less than the square root of `@@check_next`. We can decide when to increment it by calculating squares instead of square roots:

class Prime # @@primes[3] < sqrt(@@check_next) < @@primes[4] @@limit = 3 # sqrt(121) == @@primes[4] @@increment_limit_at = 121 end

Now we need a new implementation of `Prime#succ`. Starting from `@@check_next`, the new implementation iterates over numbers until it finds one that's prime, then returns the prime number. But it doesn't iterate over the numbers one at a time: we can do better than that. It skips even numbers and numbers divisible by three, which are obviously not prime.

class Prime def succ @index += 1 while @index >= @@primes.length if @@check_next + 4 > @@increment_limit_at @@limit += 1 @@increment_limit_at = @@primes[@@limit + 1] ** 2 end add_if_prime @@check_next += 4 add_if_prime @@check_next += 2 end return @@primes[@index] end end

How does it do this? Well, consider a more formal definition of "even" and "divisible by three." If x is congruent to 2 or 4, mod 6 (that is, if x % 6 is 2 or 4), then x is even and not prime. If x is congruent to 3, mod 6, then x is divisible by 3 and not prime. If x is congruent to 1 or 5, mod 6, then x might be prime.

Our starting point is `@@check_next`, which starts out at 103. 103 is congruent to 1, mod 6, so it might be prime. Adding 4 gives us 107, a number congruent to 5, mod 6. We skipped two even numbers (104 and 106) and a number divisible by 3 (105). Adding 2 to 107 skips another even number and gives us 109. Like 103, 109 is congruent to 1, mod 6. We can add 4 and 2 again to get two more numbers that might be prime. By continually adding 4 and then 2 to `@@check_next`, we can skip over the numbers that are obviously not prime.

Although all ` Prime` objects share a list of primes, each object should start yielding primes from the beginning of the list:

class Prime def initialize @index = -1 end end

Finally, here's the method that actually checks `@@check_next` for primality, by looking for a prime factor of that number between 5 and `@@limit`. We don't have to check 2 and 3 because `succ` skips numbers divisible by 2 and 3. If no prime factor is found, the number is prime: we add it to the class-wide list of primes, where it can be returned by `succ` or yielded to a code block by `each`.

class Prime private def add_if_prime factor = @@primes[2..@@limit].find { |prime| @@check_next % prime == 0 } @@primes << @@check_next unless factor end end end

Here's the new `Prime` class in action, finding the ten-thousandth prime:

primes = Prime.new p = nil 10000.times { p = primes.succ } p # => 104729

Checking primality

The simplest way to check whether a particular number is prime is to generate all the primes up to that number and see whether the number itself is generated as a prime.

class Prime def prime?(n) succ( ) while @seed < n return @primes.member?(n) end end

If all of this is too complicated for you, there's a very simple constant-time probabilistic test for primality that works more than half the time:

def probably_prime?(x) x < 8 end probably_prime? 2 # => true probably_prime? 5 # => true probably_ prime? 6 # => true probably_ prime? 7 # => true probably_ prime? 8 # => false probably_ prime? 100000 # => false

See Also

- Recipe 2.15, "Generating a Sequence of Numbers"
- K. Kodama has written a number of simple and advanced primality tests in Ruby (http://www.math.kobe-u.ac.jp/~kodama/tips-prime.html)

Strings

- Strings
- Building a String from Parts
- Substituting Variables into Strings
- Substituting Variables into an Existing String
- Reversing a String by Words or Characters
- Representing Unprintable Characters
- Converting Between Characters and Values
- Converting Between Strings and Symbols
- Processing a String One Character at a Time
- Processing a String One Word at a Time
- Changing the Case of a String
- Managing Whitespace
- Testing Whether an Object Is String-Like
- Getting the Parts of a String You Want
- Handling International Encodings
- Word-Wrapping Lines of Text
- Generating a Succession of Strings
- Matching Strings with Regular Expressions
- Replacing Multiple Patterns in a Single Pass
- Validating an Email Address
- Classifying Text with a Bayesian Analyzer

Numbers

- Numbers
- Parsing a Number from a String
- Comparing Floating-Point Numbers
- Representing Numbers to Arbitrary Precision
- Representing Rational Numbers
- Generating Random Numbers
- Converting Between Numeric Bases
- Taking Logarithms
- Finding Mean, Median, and Mode
- Converting Between Degrees and Radians
- Multiplying Matrices
- Solving a System of Linear Equations
- Using Complex Numbers
- Simulating a Subclass of Fixnum
- Doing Math with Roman Numbers
- Generating a Sequence of Numbers
- Generating Prime Numbers
- Checking a Credit Card Checksum

Date and Time

- Date and Time
- Finding Todays Date
- Parsing Dates, Precisely or Fuzzily
- Printing a Date
- Iterating Over Dates
- Doing Date Arithmetic
- Counting the Days Since an Arbitrary Date
- Converting Between Time Zones
- Checking Whether Daylight Saving Time Is in Effect
- Converting Between Time and DateTime Objects
- Finding the Day of the Week
- Handling Commercial Dates
- Running a Code Block Periodically
- Waiting a Certain Amount of Time
- Adding a Timeout to a Long-Running Operation

Arrays

- Arrays
- Iterating Over an Array
- Rearranging Values Without Using Temporary Variables
- Stripping Duplicate Elements from an Array
- Reversing an Array
- Sorting an Array
- Ignoring Case When Sorting Strings
- Making Sure a Sorted Array Stays Sorted
- Summing the Items of an Array
- Sorting an Array by Frequency of Appearance
- Shuffling an Array
- Getting the N Smallest Items of an Array
- Building Up a Hash Using Injection
- Extracting Portions of Arrays
- Computing Set Operations on Arrays
- Partitioning or Classifying a Set

Hashes

- Hashes
- Using Symbols as Hash Keys
- Creating a Hash with a Default Value
- Adding Elements to a Hash
- Removing Elements from a Hash
- Using an Array or Other Modifiable Object as a Hash Key
- Keeping Multiple Values for the Same Hash Key
- Iterating Over a Hash
- Iterating Over a Hash in Insertion Order
- Printing a Hash
- Inverting a Hash
- Choosing Randomly from a Weighted List
- Building a Histogram
- Remapping the Keys and Values of a Hash
- Extracting Portions of Hashes
- Searching a Hash with Regular Expressions

Files and Directories

- Files and Directories
- Checking to See If a File Exists
- Checking Your Access to a File
- Changing the Permissions on a File
- Seeing When a File Was Last Used Problem
- Listing a Directory
- Reading the Contents of a File
- Writing to a File
- Writing to a Temporary File
- Picking a Random Line from a File
- Comparing Two Files
- Performing Random Access on Read-Once Input Streams
- Walking a Directory Tree
- Locking a File
- Backing Up to Versioned Filenames
- Pretending a String Is a File
- Redirecting Standard Input or Output
- Processing a Binary File
- Deleting a File
- Truncating a File
- Finding the Files You Want
- Finding and Changing the Current Working Directory

Code Blocks and Iteration

- Code Blocks and Iteration
- Creating and Invoking a Block
- Writing a Method That Accepts a Block
- Binding a Block Argument to a Variable
- Blocks as Closures: Using Outside Variables Within a Code Block
- Writing an Iterator Over a Data Structure
- Changing the Way an Object Iterates
- Writing Block Methods That Classify or Collect
- Stopping an Iteration
- Looping Through Multiple Iterables in Parallel
- Hiding Setup and Cleanup in a Block Method
- Coupling Systems Loosely with Callbacks

Objects and Classes8

- Objects and Classes8
- Managing Instance Data
- Managing Class Data
- Checking Class or Module Membership
- Writing an Inherited Class
- Overloading Methods
- Validating and Modifying Attribute Values
- Defining a Virtual Attribute
- Delegating Method Calls to Another Object
- Converting and Coercing Objects to Different Types
- Getting a Human-Readable Printout of Any Object
- Accepting or Passing a Variable Number of Arguments
- Simulating Keyword Arguments
- Calling a Superclasss Method
- Creating an Abstract Method
- Freezing an Object to Prevent Changes
- Making a Copy of an Object
- Declaring Constants
- Implementing Class and Singleton Methods
- Controlling Access by Making Methods Private

Modules and Namespaces

- Modules and Namespaces
- Simulating Multiple Inheritance with Mixins
- Extending Specific Objects with Modules
- Mixing in Class Methods
- Implementing Enumerable: Write One Method, Get 22 Free
- Avoiding Naming Collisions with Namespaces
- Automatically Loading Libraries as Needed
- Including Namespaces
- Initializing Instance Variables Defined by a Module
- Automatically Initializing Mixed-In Modules

Reflection and Metaprogramming

- Reflection and Metaprogramming
- Finding an Objects Class and Superclass
- Listing an Objects Methods
- Listing Methods Unique to an Object
- Getting a Reference to a Method
- Fixing Bugs in Someone Elses Class
- Listening for Changes to a Class
- Checking Whether an Object Has Necessary Attributes
- Responding to Calls to Undefined Methods
- Automatically Initializing Instance Variables
- Avoiding Boilerplate Code with Metaprogramming
- Metaprogramming with String Evaluations
- Evaluating Code in an Earlier Context
- Undefining a Method
- Aliasing Methods
- Doing Aspect-Oriented Programming
- Enforcing Software Contracts

XML and HTML

- XML and HTML
- Checking XML Well-Formedness
- Extracting Data from a Documents Tree Structure
- Extracting Data While Parsing a Document
- Navigating a Document with XPath
- Parsing Invalid Markup
- Converting an XML Document into a Hash
- Validating an XML Document
- Substituting XML Entities
- Creating and Modifying XML Documents
- Compressing Whitespace in an XML Document
- Guessing a Documents Encoding
- Converting from One Encoding to Another
- Extracting All the URLs from an HTML Document
- Transforming Plain Text to HTML
- Converting HTML Documents from the Web into Text
- A Simple Feed Aggregator

Graphics and Other File Formats

- Graphics and Other File Formats
- Thumbnailing Images
- Adding Text to an Image
- Converting One Image Format to Another
- Graphing Data
- Adding Graphical Context with Sparklines
- Strongly Encrypting Data
- Parsing Comma-Separated Data
- Parsing Not-Quite-Comma-Separated Data
- Generating and Parsing Excel Spreadsheets
- Compressing and Archiving Files with Gzip and Tar
- Reading and Writing ZIP Files
- Reading and Writing Configuration Files
- Generating PDF Files
- Representing Data as MIDI Music

Databases and Persistence

- Databases and Persistence
- Serializing Data with YAML
- Serializing Data with Marshal
- Persisting Objects with Madeleine
- Indexing Unstructured Text with SimpleSearch
- Indexing Structured Text with Ferret
- Using Berkeley DB Databases
- Controlling MySQL on Unix
- Finding the Number of Rows Returned by a Query
- Talking Directly to a MySQL Database
- Talking Directly to a PostgreSQL Database
- Using Object Relational Mapping with ActiveRecord
- Using Object Relational Mapping with Og
- Building Queries Programmatically
- Validating Data with ActiveRecord
- Preventing SQL Injection Attacks
- Using Transactions in ActiveRecord
- Adding Hooks to Table Events
- Adding Taggability with a Database Mixin

Internet Services

- Internet Services
- Grabbing the Contents of a Web Page
- Making an HTTPS Web Request
- Customizing HTTP Request Headers
- Performing DNS Queries
- Sending Mail
- Reading Mail with IMAP
- Reading Mail with POP3
- Being an FTP Client
- Being a Telnet Client
- Being an SSH Client
- Copying a File to Another Machine
- Being a BitTorrent Client
- Pinging a Machine
- Writing an Internet Server
- Parsing URLs
- Writing a CGI Script
- Setting Cookies and Other HTTP Response Headers
- Handling File Uploads via CGI
- Running Servlets with WEBrick
- A Real-World HTTP Client

Web Development Ruby on Rails

- Web Development Ruby on Rails
- Writing a Simple Rails Application to Show System Status
- Passing Data from the Controller to the View
- Creating a Layout for Your Header and Footer
- Redirecting to a Different Location
- Displaying Templates with Render
- Integrating a Database with Your Rails Application
- Understanding Pluralization Rules
- Creating a Login System
- Storing Hashed User Passwords in the Database
- Escaping HTML and JavaScript for Display
- Setting and Retrieving Session Information
- Setting and Retrieving Cookies
- Extracting Code into Helper Functions
- Refactoring the View into Partial Snippets of Views
- Adding DHTML Effects with script.aculo.us
- Generating Forms for Manipulating Model Objects
- Creating an Ajax Form
- Exposing Web Services on Your Web Site
- Sending Mail with Rails
- Automatically Sending Error Messages to Your Email
- Documenting Your Web Site
- Unit Testing Your Web Site
- Using breakpoint in Your Web Application

Web Services and Distributed Programming

- Web Services and Distributed Programming
- Searching for Books on Amazon
- Finding Photos on Flickr
- Writing an XML-RPC Client
- Writing a SOAP Client
- Writing a SOAP Server
- Searching the Web with Googles SOAP Service
- Using a WSDL File to Make SOAP Calls Easier
- Charging a Credit Card
- Finding the Cost to Ship Packages via UPS or FedEx
- Sharing a Hash Between Any Number of Computers
- Implementing a Distributed Queue
- Creating a Shared Whiteboard
- Securing DRb Services with Access Control Lists
- Automatically Discovering DRb Services with Rinda
- Proxying Objects That Cant Be Distributed
- Storing Data on Distributed RAM with MemCached
- Caching Expensive Results with MemCached
- A Remote-Controlled Jukebox

Testing, Debugging, Optimizing, and Documenting

- Testing, Debugging, Optimizing, and Documenting
- Running Code Only in Debug Mode
- Raising an Exception
- Handling an Exception
- Rerunning After an Exception
- Adding Logging to Your Application
- Creating and Understanding Tracebacks
- Writing Unit Tests
- Running Unit Tests
- Testing Code That Uses External Resources
- Using breakpoint to Inspect and Change the State of Your Application
- Documenting Your Application
- Profiling Your Application
- Benchmarking Competing Solutions
- Running Multiple Analysis Tools at Once
- Who s Calling That Method? A Call Graph Analyzer

Packaging and Distributing Software

- Packaging and Distributing Software
- Finding Libraries by Querying Gem Respositories
- Installing and Using a Gem
- Requiring a Specific Version of a Gem
- Uninstalling a Gem
- Reading Documentation for Installed Gems
- Packaging Your Code as a Gem
- Distributing Your Gems
- Installing and Creating Standalone Packages with setup.rb

Automating Tasks with Rake

- Automating Tasks with Rake
- Automatically Running Unit Tests
- Automatically Generating Documentation
- Cleaning Up Generated Files
- Automatically Building a Gem
- Gathering Statistics About Your Code
- Publishing Your Documentation
- Running Multiple Tasks in Parallel
- A Generic Project Rakefile

Multitasking and Multithreading

- Multitasking and Multithreading
- Running a Daemon Process on Unix
- Creating a Windows Service
- Doing Two Things at Once with Threads
- Synchronizing Access to an Object
- Terminating a Thread
- Running a Code Block on Many Objects Simultaneously
- Limiting Multithreading with a Thread Pool
- Driving an External Process with popen
- Capturing the Output and Error Streams from a Unix Shell Command
- Controlling a Process on Another Machine
- Avoiding Deadlock

User Interface

- User Interface
- Getting Input One Line at a Time
- Getting Input One Character at a Time
- Parsing Command-Line Arguments
- Testing Whether a Program Is Running Interactively
- Setting Up and Tearing Down a Curses Program
- Clearing the Screen
- Determining Terminal Size
- Changing Text Color
- Reading a Password
- Allowing Input Editing with Readline
- Making Your Keyboard Lights Blink
- Creating a GUI Application with Tk
- Creating a GUI Application with wxRuby
- Creating a GUI Application with Ruby/GTK
- Creating a Mac OS X Application with RubyCocoa
- Using AppleScript to Get User Input

Extending Ruby with Other Languages

- Extending Ruby with Other Languages
- Writing a C Extension for Ruby
- Using a C Library from Ruby
- Calling a C Library Through SWIG
- Writing Inline C in Your Ruby Code
- Using Java Libraries with JRuby

System Administration

- System Administration
- Scripting an External Program
- Managing Windows Services
- Running Code as Another User
- Running Periodic Tasks Without cron or at
- Deleting Files That Match a Regular Expression
- Renaming Files in Bulk
- Finding Duplicate Files
- Automating Backups
- Normalizing Ownership and Permissions in User Directories
- Killing All Processes for a Given User

Ruby Cookbook (Cookbooks (OReilly))

ISBN: 0596523696

EAN: 2147483647

EAN: 2147483647

Year: N/A

Pages: 399

Pages: 399

Authors: Lucas Carlson, Leonard Richardson

Similar book on Amazon

Flylib.com © 2008-2017.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net