Sequence of primes by trial division: Difference between revisions
Sequence of primes by trial division (view source)
Revision as of 23:06, 18 January 2021
, 3 years ago→{{header|PicoLisp}}
Line 1,828:
{{out}}
<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}}==
| |||