Use math.primes.erato instead of a list of first prime numbers

diff --git a/extra/math/primes/primes-docs.factor b/extra/math/primes/primes-docs.factor
index 1077659d5ecef0bcb393c4cbf82d26c0192352e3..516b081624eb5c1135d3f8a604c872de559e6c53 100644 (file)
--- a/extra/math/primes/primes-docs.factor
+++ b/extra/math/primes/primes-docs.factor
@@ -4,7 +4,7 @@ IN: math.primes
 { next-prime prime? } related-words
 
 HELP: next-prime
-{ $values { "n" "a positive integer" } { "p" "a prime number" } }
+{ $values { "n" "an integer not smaller than 2" } { "p" "a prime number" } }
 { $description "Return the next prime number greater than " { $snippet "n" } "." } ;
 
 HELP: prime?

diff --git a/extra/math/primes/primes-tests.factor b/extra/math/primes/primes-tests.factor
index 186acc9b1127d3b3808e2fe6221b00bbbaa30ecd..b0b25285c0acab325780dd0af339631b5e91a523 100644 (file)
--- a/extra/math/primes/primes-tests.factor
+++ b/extra/math/primes/primes-tests.factor
@@ -8,3 +8,7 @@ USING: arrays math.primes tools.test lists.lazy ;
 { { 999983 1000003 } } [ 2 999982 lprimes-from ltake list>array ] unit-test
 { { 2 3 5 7 } } [ 10 primes-upto >array ] unit-test
 { { 999983 1000003 } } [ 999982 1000010 primes-between >array ] unit-test
+
+{ { 4999963 4999999 5000011 5000077 5000081 } }
+[ 4999962 5000082 primes-between >array ]
+unit-test

diff --git a/extra/math/primes/primes.factor b/extra/math/primes/primes.factor
index d93910ec02f0172079bb44d4ee59e4a1c62c384d..c8f398863fe1fe46dcf1d4de2f1a18657795f8f2 100644 (file)
--- a/extra/math/primes/primes.factor
+++ b/extra/math/primes/primes.factor
@@ -1,46 +1,39 @@
 ! Copyright (C) 2007 Samuel Tardieu.
 ! See http://factorcode.org/license.txt for BSD license.
 USING: binary-search combinators kernel lists.lazy math math.functions
-    math.miller-rabin math.primes.list sequences ;
+math.miller-rabin math.primes.erato math.ranges sequences ;
 IN: math.primes
 
 <PRIVATE
 
-: find-prime-miller-rabin ( n -- p )
-    [ dup miller-rabin ] [ 2 + ] [ ] until ; foldable
+: look-in-bitmap ( n -- ? ) >index 4999999 sieve nth ;
 
-PRIVATE>
+: really-prime? ( n -- ? )
+    dup 5000000 < [ look-in-bitmap ] [ miller-rabin ] if ; foldable
 
-: next-prime ( n -- p )
-    dup 999983 < [
-        primes-under-million [ natural-search drop 1+ ] keep nth
-    ] [
-        next-odd find-prime-miller-rabin
-    ] if ; foldable
+PRIVATE>
 
 : prime? ( n -- ? )
-    dup 1000000 < [
-        dup primes-under-million natural-search nip =
-    ] [
-        miller-rabin
-    ] if ; foldable
+    {
+        { [ dup 2 < ] [ drop f ] }
+        { [ dup even? ] [ 2 = ] }
+        [ really-prime? ]
+    } cond ; foldable
+
+: next-prime ( n -- p )
+    next-odd [ dup really-prime? ] [ 2 + ] [ ] until ; foldable
 
-: lprimes ( -- list )
-    0 primes-under-million seq>list
-    1000003 [ 2 + find-prime-miller-rabin ] lfrom-by
-    lappend ;
+: lprimes ( -- list ) 2 [ next-prime ] lfrom-by ;
 
 : lprimes-from ( n -- list )
     dup 3 < [ drop lprimes ] [ 1- next-prime [ next-prime ] lfrom-by ] if ;
 
 : primes-upto ( n -- seq )
-    {
-        { [ dup 2 < ] [ drop { } ] }
-        { [ dup 1000003 < ] [
-            primes-under-million [ natural-search drop 1+ 0 swap ] keep <slice>
-        ] }
-        [ lprimes swap [ <= ] curry lwhile list>array ]
-    } cond ; foldable
+    dup 2 < [
+        drop V{ }
+    ] [
+        3 swap 2 <range> [ prime? ] filter 2 prefix
+    ] if ; foldable
 
 : primes-between ( low high -- seq )
     primes-upto [ 1- next-prime ] dip