X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=primes.rb;h=496e79099c72f5e3d968e5798833d759d1b0e65c;hb=HEAD;hp=0febe8007f617dd2b3ecbca2eae02a72ef41cd57;hpb=b0fb3e87a6e12cfe1203e44aed2caaf7b7d8c959;p=project-euler.git

diff --git a/primes.rb b/primes.rb
index 0febe80..496e790 100644
--- a/primes.rb
+++ b/primes.rb
@@ -3,6 +3,7 @@
 # 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
 
@@ -14,22 +15,32 @@ class Primes
   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 = 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
 
+  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 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)
+      limit = Math.sqrt(candidate).floor
+      index = @primes.bsearch_index {|i| i > limit} || @primes.length
     end
     candidate
   end
@@ -54,7 +65,7 @@ class Primes
   end
 
   def add_next_prime!
-    @primes.push next_prime
+    @primes << next_prime
   end
 
   # No longer needed: use Enumerable#take_while instead
@@ -90,11 +101,32 @@ class Primes
   end
   
   def include?(n)
-    while n >= @primes.max
+    while n >= @primes.last
       add_next_prime!
     end
-    @primes.include?(n)
+    !!(@primes.bsearch {|i| n - i})
+  end
+
+  # Use this if you're only testing a few primes and not needing to generate many more.
+  def is_prime?(n)
+    return true if n == 2
+    return false if n < 2
+    limit = Math.sqrt(n).floor
+    while @primes.last <= limit
+      add_next_prime!
+    end
+    index = @primes.bsearch_index {|i| i > limit} || @primes.length
+    @primes[0..index].none? {|i| n % i == 0}
   end
 
 end
 
+
+class Integer
+  @@primes = Primes.instance
+  
+  def prime?
+    @@primes.include? self
+    # @@primes.is_prime? self
+  end
+end