1 # A faster Prime number library
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
15 attr_accessor
:mod_candidates
20 # @primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
23 @mod_candidates = ((1..@cache_up_to).collect
{|x
| x
}).select
{|x
| [2, 3, 5].all
? {|p
| x
% p
!= 0}}
26 def load_primes(cache_file
)
27 if File
.file
?(cache_file
)
28 @primes = File
.readlines(cache_file
).map
{|l
| l
.chomp
.to_i
}
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
51 add_next_prime
! if i
>= @primes.length
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]
62 next_candidate
= candidate
.div(@cache_up_to) * @cache_up_to + c_increments
.first
71 # No longer needed: use Enumerable#take_while instead
73 # add_next_prime! while not yield(@primes)
79 if @primes.length
<= n
80 (n
- @primes.length
+ 1).times
{ add_next_prime
! }
81 # primes_until {|ps| ps.length > n}
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
|
94 # stop if we're too high already
96 # remove all multiples of this number
97 (p
*p
).step(limit
, p
){ |m
| candidates
[m
] = nil}
104 while n
>= @primes.last
107 !!(@primes.bsearch
{|i
| n
- i
})
110 # Use this if you're only testing a few primes and not needing to generate many more.
112 return true if n
== 2
113 return false if n
< 2
114 limit
= Math
.sqrt(n
).floor
115 while @primes.last
<= limit
118 index
= @primes.bsearch_index
{|i
| i
> limit
} || @primes.length
119 @primes[0..index
].none
? {|i
| n
% i
== 0}
126 @
@primes = Primes
.instance
129 @
@primes.include? self
130 # @@primes.is_prime? self