1 # A faster Prime number library
5 # primes = Primes.instance
6 # primes.take(20) # returns the first 20 primes
7 # primes[10000] # returns the 10,001st prime
14 attr_accessor
:mod_candidates
18 def initialize(sieve_limit
= 10000)
19 # @primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
20 @primes = sieve sieve_limit
22 @mod_candidates = ((1..@cache_up_to).collect
{|x
| x
}).select
{|x
| [2, 3, 5].all
? {|p
| x
% p
!= 0}}
30 candidate
= next_candidate(@primes[-1])
31 while @primes.any
? {|i
| candidate
% i
== 0 }
32 candidate
= next_candidate(candidate
)
40 add_next_prime
! if i
>= @primes.length
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]
51 next_candidate
= candidate
.div(@cache_up_to) * @cache_up_to + c_increments
.first
57 @primes.push next_prime
60 # No longer needed: use Enumerable#take_while instead
62 # add_next_prime! while not yield(@primes)
68 if @primes.length
<= n
69 (n
- @primes.length
+ 1).times
{ add_next_prime
! }
70 # primes_until {|ps| ps.length > n}
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
|
83 # stop if we're too high already
85 # remove all multiples of this number
86 (p
*p
).step(limit
, p
){ |m
| candidates
[m
] = nil}
93 while n
>= @primes.max