1 ! Copyright (C) 2007 Samuel Tardieu.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: binary-search combinators kernel lists.lazy math math.functions
4 math.miller-rabin math.primes.list sequences ;
9 : find-prime-miller-rabin ( n -- p )
10 dup miller-rabin [ 2 + find-prime-miller-rabin ] unless ; foldable
14 : next-prime ( n -- p )
16 primes-under-million [ natural-search drop 1+ ] keep nth
18 next-odd find-prime-miller-rabin
23 dup primes-under-million natural-search nip =
29 0 primes-under-million seq>list
30 1000003 [ 2 + find-prime-miller-rabin ] lfrom-by
33 : lprimes-from ( n -- list )
34 dup 3 < [ drop lprimes ] [ 1- next-prime [ next-prime ] lfrom-by ] if ;
36 : primes-upto ( n -- seq )
38 { [ dup 2 < ] [ drop { } ] }
40 primes-under-million [ natural-search drop 1+ 0 swap ] keep <slice>
42 [ primes-under-million 1000003 lprimes-from
43 rot [ <= ] curry lwhile list>array append ]
46 : primes-between ( low high -- seq )
47 primes-upto [ 1- next-prime ] dip
48 [ natural-search drop ] [ length ] [ ] tri <slice> ; foldable
50 : coprime? ( a b -- ? ) gcd nip 1 = ; foldable