Done puzzle 64
[project-euler.git] / 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