primes.rb

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