From 46afc3b90a7bed5b5a44f812c631949edd23307c Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Thu, 16 Feb 2017 14:04:29 +0000 Subject: [PATCH] Made the primes library faster --- euler35.rb | 5 +++-- primes.rb | 9 ++++++--- 2 files changed, 9 insertions(+), 5 deletions(-) diff --git a/euler35.rb b/euler35.rb index ebe8450..d2ba75d 100644 --- a/euler35.rb +++ b/euler35.rb @@ -36,10 +36,11 @@ class Integer end -(10**6).prime? - RubyProf.start +# (10**6).prime? + + pl0 = 0.pl beginning_time = Time.now cps = (2..10**6).select {|n| n.circular_prime?} diff --git a/primes.rb b/primes.rb index 0febe80..23fd447 100644 --- a/primes.rb +++ b/primes.rb @@ -28,7 +28,9 @@ class Primes 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 @@ -90,10 +92,11 @@ class Primes end def include?(n) - while n >= @primes.max + while n >= @primes.last add_next_prime! end - @primes.include?(n) + # @primes.include?(n) + !!(@primes.bsearch {|i| n - i}) end end -- 2.34.1