Primality by trial division: Difference between revisions
→{{header|Racket}}: move Racket sieves here from Sieve of Eratosthenes, as per discussion on the talk page of SoE; use standard whitespace formatting
(→Sieve by trial division: c/e, clarify) |
(→{{header|Racket}}: move Racket sieves here from Sieve of Eratosthenes, as per discussion on the talk page of SoE; use standard whitespace formatting) |
||
Line 1,863:
(else (for/and ((i (in-range 3 (ceiling (sqrt number)))))
(not (zero? (remainder number i)))))))</lang>
=== Infinite list of primes ===
==== using laziness ====
This example uses infinite lists (streams), and it is a classic code that some has claimed an [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "unfaithful sieve"].
<lang Racket>#lang lazy
;; infinite list using lazy racket (see the language above)
(define nats (cons 1 (map add1 nats)))
(define (sift n l) (filter (λ(x) (not (zero? (modulo x n)))) l))
(define (sieve l) (cons (first l) (sieve (sift (first l) (rest l)))))
(define primes (sieve (rest nats)))
(define (take-upto n l)
(if (<= (car l) n) (cons (car l) (take-upto n (cdr l))) '()))
(!! (take-upto 100 primes))</lang>
==== using threads and channels ====
Same as above. Infinite list using threads and channels (similar to newsqueak).
<lang Racket>#lang racket
(define-syntax (bg-loop stx)
(syntax-case stx ()
[(_ expr ...)
(with-syntax ([out! (datum->syntax stx 'out!)])
#'(let ([out (make-channel)])
(define (out! x) (channel-put out x))
(thread (λ() (let loop () expr ... (loop))))
out))]))
(define nats (bg-loop (for ([i (in-naturals 1)]) (out! i))))
(define (filter pred? c)
(bg-loop (define x (channel-get c))
(when (pred? x) (out! x))))
(define (sift n c)
(filter (λ(x) (not (zero? (modulo x n)))) c))
(define (sieve c)
(bg-loop (define x (channel-get c))
(out! x)
(set! c (sift x c))))
(define primes (begin (channel-get nats) (sieve nats)))
(define (take-upto n c)
(let loop ()
(let ([x (channel-get c)]) (if (<= x n) (cons x (loop)) '()))))
(take-upto 100 primes)</lang>
==== using generators ====
Yet another variation of the same algorithm as above, this time using generators.
<lang Racket>#lang racket
(require racket/generator)
(define nats (generator () (for ([i (in-naturals 1)]) (yield i))))
(define (filter pred g)
(generator () (for ([i (in-producer g #f)] #:when (pred i)) (yield i))))
(define (sift n g) (filter (λ(x) (not (zero? (modulo x n)))) g))
(define (sieve g)
(generator ()
(let loop ([g g]) (let ([x (g)]) (yield x) (loop (sift x g))))))
(define primes (begin (nats) (sieve nats)))
(define (take-upto n p)
(let loop ()
(let ([x (p)]) (if (<= x n) (cons x (loop)) '()))))
(take-upto 100 primes)</lang>
=={{header|REBOL}}==
| |||