projects
/
project-euler.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Done puzzle 58
[project-euler.git]
/
primes.rb
diff --git
a/primes.rb
b/primes.rb
index b254fab4f52ac97852e7f5867a5bb311960f3cde..496e79099c72f5e3d968e5798833d759d1b0e65c 100644
(file)
--- a/
primes.rb
+++ b/
primes.rb
@@
-3,6
+3,7
@@
# To use:
# require 'primes.rb'
# primes = Primes.instance
# To use:
# require 'primes.rb'
# primes = Primes.instance
+# primes.load_primes 'primes_1000000.txt' # loads a file of precomputed primes
# primes.take(20) # returns the first 20 primes
# primes[10000] # returns the 10,001st prime
# primes.take(20) # returns the first 20 primes
# primes[10000] # returns the 10,001st prime
@@
-14,14
+15,20
@@
class Primes
attr_accessor :mod_candidates
include Singleton
attr_accessor :mod_candidates
include Singleton
-
- def initialize(
sieve_limit = 10000
)
+
+ def initialize()
# @primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
# @primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
- @primes = sieve
sieve_limit
+ @primes = sieve
@cache_up_to = 30
@mod_candidates = ((1..@cache_up_to).collect {|x| x}).select {|x| [2, 3, 5].all? {|p| x % p != 0}}
end
@cache_up_to = 30
@mod_candidates = ((1..@cache_up_to).collect {|x| x}).select {|x| [2, 3, 5].all? {|p| x % p != 0}}
end
+ def load_primes(cache_file)
+ if File.file?(cache_file)
+ @primes = File.readlines(cache_file).map {|l| l.chomp.to_i}
+ end
+ end
+
def primes
@primes.dup
end
def primes
@primes.dup
end
@@
-32,6
+39,8
@@
class Primes
index = @primes.bsearch_index {|i| i > limit} || @primes.length
while @primes[0..index].any? {|i| candidate % i == 0 }
candidate = next_candidate(candidate)
index = @primes.bsearch_index {|i| i > limit} || @primes.length
while @primes[0..index].any? {|i| candidate % i == 0 }
candidate = next_candidate(candidate)
+ limit = Math.sqrt(candidate).floor
+ index = @primes.bsearch_index {|i| i > limit} || @primes.length
end
candidate
end
end
candidate
end
@@
-56,7
+65,7
@@
class Primes
end
def add_next_prime!
end
def add_next_prime!
- @primes
.push
next_prime
+ @primes
<<
next_prime
end
# No longer needed: use Enumerable#take_while instead
end
# No longer needed: use Enumerable#take_while instead