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 37
[project-euler.git]
/
primes.rb
diff --git
a/primes.rb
b/primes.rb
index 0febe8007f617dd2b3ecbca2eae02a72ef41cd57..7e2cfaacaa817e2418271d2544961271b0bb245a 100644
(file)
--- a/
primes.rb
+++ b/
primes.rb
@@
-28,7
+28,9
@@
class Primes
def next_prime
candidate = next_candidate(@primes[-1])
def next_prime
candidate = next_candidate(@primes[-1])
- while @primes.any? {|i| candidate % i == 0 }
+ limit = Math.sqrt(candidate).floor
+ index = @primes.bsearch_index {|i| i > limit} || @primes.length
+ while @primes[0..index].any? {|i| candidate % i == 0 }
candidate = next_candidate(candidate)
end
candidate
candidate = next_candidate(candidate)
end
candidate
@@
-90,11
+92,20
@@
class Primes
end
def include?(n)
end
def include?(n)
- while n >= @primes.
max
+ while n >= @primes.
last
add_next_prime!
end
add_next_prime!
end
- @primes.include?(n)
+ # @primes.include?(n)
+ !!(@primes.bsearch {|i| n - i})
end
end
end
end
+
+class Integer
+ @@primes = Primes.instance
+
+ def prime?
+ @@primes.include? self
+ end
+end