Done puzzle 37
[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.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.include?(n)
99 !!(@primes.bsearch {|i| n - i})
100 end
101
102 end
103
104
105 class Integer
106 @@primes = Primes.instance
107
108 def prime?
109 @@primes.include? self
110 end
111 end