primes.rb

   1 # A faster Prime number library
   2
   3 # To use:
   4 # require 'primes.rb'
   5 # primes = Primes.instance
   6 # primes.take(20) # returns the first 20 primes
   7 # primes[10000]   # returns the 10,001st prime
   8
   9 require 'singleton'
  10
  11 class Primes
  12   include Enumerable
  13
  14   attr_accessor :mod_candidates
  15
  16   include Singleton
  17
  18   def initialize(sieve_limit = 10000)
  19     # @primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
  20     @primes = sieve sieve_limit
  21     @cache_up_to = 30
  22     @mod_candidates = ((1..@cache_up_to).collect {|x| x}).select {|x| [2, 3, 5].all? {|p| x % p != 0}}
  23   end
  24
  25   def primes
  26     @primes.dup
  27   end
  28
  29   def next_prime
  30     candidate = next_candidate(@primes[-1])
  31     limit = Math.sqrt(candidate).floor
  32     index = @primes.bsearch_index {|i| i > limit} || @primes.length
  33     while @primes[0..index].any? {|i| candidate % i == 0 }
  34       candidate = next_candidate(candidate)
  35     end
  36     candidate
  37   end
  38
  39   def each &block
  40     i = 0
  41     while true do
  42       add_next_prime! if i >= @primes.length
  43       block.call @primes[i]
  44       i += 1
  45     end
  46   end
  47
  48   def next_candidate(candidate)
  49     c_increments = @mod_candidates.select {|c| c > candidate % @cache_up_to}
  50     if c_increments.empty?
  51       next_candidate = (candidate.div(@cache_up_to) + 1) * @cache_up_to + @mod_candidates[0]
  52     else
  53       next_candidate = candidate.div(@cache_up_to) * @cache_up_to + c_increments.first
  54     end
  55     next_candidate
  56   end
  57
  58   def add_next_prime!
  59     @primes.push next_prime
  60   end
  61
  62   # No longer needed: use Enumerable#take_while instead
  63 #   def primes_until
  64 #     add_next_prime! while not yield(@primes)
  65 #     @primes
  66 #   end
  67
  68   # the nth prime
  69   def [](n)
  70     if @primes.length <= n
  71       (n - @primes.length + 1).times { add_next_prime! }
  72       # primes_until {|ps| ps.length > n}
  73     end
  74     @primes[n]
  75   end
  76
  77   # Perform sieve of Eratosthenes
  78   # Algorithm courtesy of Marc Seeger at http://blog.marc-seeger.de/2010/12/05/prime-numbers-in-ruby/
  79   def sieve(limit = 10000)
  80     candidates = [nil, nil] + (2..limit).to_a
  81     stop_at = Math.sqrt(limit).floor
  82     candidates.each do |p|
  83       # jump over nils
  84       next unless p
  85       # stop if we're too high already
  86       break if p > stop_at
  87       # remove all multiples of this number
  88       (p*p).step(limit, p){ |m| candidates[m] = nil}
  89     end
  90     #remove unwanted nils
  91     candidates.compact
  92   end
  93
  94   def include?(n)
  95     while n >= @primes.last
  96       add_next_prime!
  97     end
  98     !!(@primes.bsearch {|i| n - i})
  99   end
 100
 101   # Use this if you're only testing a few primes and not needing to generate many more.
 102   def is_prime?(n)
 103     return true if n == 2
 104     return false if n < 2
 105     limit = Math.sqrt(n).floor
 106     while @primes.last <= limit
 107       add_next_prime!
 108     end
 109     index = @primes.bsearch_index {|i| i > limit} || @primes.length
 110     @primes[0..index].none? {|i| n % i == 0}
 111   end
 112
 113 end
 114
 115
 116 class Integer
 117   @@primes = Primes.instance
 118
 119   def prime?
 120     @@primes.include? self
 121     # @@primes.is_prime? self
 122   end
 123 end