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     while @primes.any? {|i| candidate % i == 0 }
  32       candidate = next_candidate(candidate)
  33     end
  34     candidate
  35   end
  36
  37   def each &block
  38     i = 0
  39     while true do
  40       add_next_prime! if i >= @primes.length
  41       block.call @primes[i]
  42       i += 1
  43     end
  44   end
  45
  46   def next_candidate(candidate)
  47     c_increments = @mod_candidates.select {|c| c > candidate % @cache_up_to}
  48     if c_increments.empty?
  49       next_candidate = (candidate.div(@cache_up_to) + 1) * @cache_up_to + @mod_candidates[0]
  50     else
  51       next_candidate = candidate.div(@cache_up_to) * @cache_up_to + c_increments.first
  52     end
  53     next_candidate
  54   end
  55
  56   def add_next_prime!
  57     @primes.push next_prime
  58   end
  59
  60   # No longer needed: use Enumerable#take_while instead
  61 #   def primes_until
  62 #     add_next_prime! while not yield(@primes)
  63 #     @primes
  64 #   end
  65
  66   # the nth prime
  67   def [](n)
  68     if @primes.length <= n
  69       (n - @primes.length + 1).times { add_next_prime! }
  70       # primes_until {|ps| ps.length > n}
  71     end
  72     @primes[n]
  73   end
  74
  75   # Perform sieve of Eratosthenes
  76   # Algorithm courtesy of Marc Seeger at http://blog.marc-seeger.de/2010/12/05/prime-numbers-in-ruby/
  77   def sieve(limit = 10000)
  78     candidates = [nil, nil] + (2..limit).to_a
  79     stop_at = Math.sqrt(limit).floor
  80     candidates.each do |p|
  81       # jump over nils
  82       next unless p
  83       # stop if we're too high already
  84       break if p > stop_at
  85       # remove all multiples of this number
  86       (p*p).step(limit, p){ |m| candidates[m] = nil}
  87     end
  88     #remove unwanted nils
  89     candidates.compact
  90   end
  91
  92   def include?(n)
  93     while n >= @primes.max
  94       add_next_prime!
  95     end
  96     @primes.include?(n)
  97   end
  98
  99 end
 100