Sequence of primes by trial division: Difference between revisions
Content added Content deleted
Line 1,828: | Line 1,828: | ||
{{out}} |
{{out}} |
||
<pre>(53 59 61 67 71 73 79 83 89 97)</pre> |
<pre>(53 59 61 67 71 73 79 83 89 97)</pre> |
||
===Unbounded generator=== |
|||
Based on Runciman, C. (1997) FUNCTIONAL PEARL : lazy wheel |
|||
sieves and spirals of primes. Journal of Functional Programming. pp. 219-225. |
|||
This is based on the wheel sieve Mark 1 in the paper, where candidates are taken from increasing size factorization wheels, where the next wheel of increasing size is used after the current wheel is completely "rolled." |
|||
<lang PicoLisp> |
|||
(de comma_fmt (N) (format N 0 "." ",")) |
|||
(de prime-td? (N Chk) |
|||
(let (D NIL Rt (sqrt N)) |
|||
(loop |
|||
(NIL Chk T) # if we run out of test divisors then it's prime. |
|||
(setq D (pop 'Chk)) |
|||
(T (> D Rt) T) |
|||
(T (=0 (% N D)) NIL)))) |
|||
(de primes (Run?) |
|||
(if (not Run?) |
|||
(co 'primegen) # stop |
|||
(co 'primegen |
|||
(yield 2) |
|||
(yield 3) |
|||
(make |
|||
(chain (3 1 2)) # start with W2 = 1, 3, 5, 7, 9, ... |
|||
(loop |
|||
# At the start of the loop, switch to the next size wheel. |
|||
(let |
|||
((Sj . Wheel) (made) # current wheel (size & spokes) |
|||
P (cadr Wheel) # current sieving prime |
|||
Sk (* P Sj) ) # size of next wheel |
|||
(made (list Sk)) |
|||
(chain |
|||
(filter '((N) (n0 (% N P))) Wheel)) |
|||
(for (O Sj (< O Sk) (+ O Sj)) |
|||
(for W Wheel |
|||
(let N (+ O W) |
|||
(when (n0 (% N P)) |
|||
(link N) |
|||
(when (prime-td? N (cdr Wheel)) |
|||
(yield N)))))))))))) |
|||
(do 31 (prin (primes T) " ")) (prinl) |
|||
(primes NIL) |
|||
(do 10000 (primes T)) |
|||
(prinl "The 10,001st prime is " (comma_fmt (primes T))) |
|||
(bye) |
|||
</lang> |
|||
{{Out}} |
|||
<pre> |
|||
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 |
|||
The 10,001st prime is 104,743 |
|||
</pre> |
|||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |