Done puzzle 33
[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 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