Jump to content

Primality by trial division: Difference between revisions

Primality by trial division (view source)

Revision as of 01:06, 12 September 2014

150 bytes removed ,  9 years ago
m
→‎Infinite list of primes: Rewritten a bit
m (→‎Infinite list of primes: Rewritten a bit)
Line 1,865:
 
=== Infinite list of primes ===
==== usingUsing laziness ====
 
This example uses infinite lists (streams), andto it isimplement a classicsieve codealgorithm that someproduces hasall claimedprime an [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "unfaithful sieve"]numbers.
 
<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)))
(!! (take-upto 10025 primes))</lang>▼
 
==== usingUsing threads and channels ====▼
(define (take-upto n l)
(if (<= (car l) n) (cons (car l) (take-upto n (cdr l))) '()))
▲(!! (take-upto 100 primes))</lang>
 
Same algorithm as above, but now using threads and channels to produce a channel of all prime numbers (similar to newsqueak). The macro at the top is a convenient wrapper around definitions of channels using a thread that feeds them.
▲==== using threads and channels ====
 
Same as above. Infinite list using threads and channels (similar to newsqueak).
 
<lang Racket>#lang racket
(define-syntax (bgdefine-thread-loop stx)▼
 
▲(define-syntax (bg-loop stx)
(syntax-case stx ()
[(_ (name . args) expr ...)
(with-syntax ([out! (datum->syntax stx 'out!)])
#'(letdefine ([outname (make-channel)]. args)
(set!define cout (sift x c))make-channel))▼
(define (out! x) (channel-put out x))
(thread (λ() (let loop () expr ... (loop))))
out))]))
(define nats (bg-thread-loop (nats) (for ([i (in-naturals 1)]) (out! i))))
(define-thread-loop (filter pred? c)
(bg-looplet (define [x (channel-get c)]) (when (pred? x) (out! x))))
(define (sift n c) (filter (λ(x) (whennot (predzero? x) (out!modulo x n)))) c))
(define-thread-loop (sift nsieve c)
(filterlet (λ([x (channel-get c)]) (notout! x) (zero?set! c (modulosift x nc)))) c))
(define primes (let ([ns (nats)]) (channel-get ns) (sieve cns)))
(for/list ([i 25] [x (bgin-loopproducer (define xλ() (channel-get cprimes)))]) x)</lang>
(out! x)
▲ (set! c (sift x c))))
(define primes (begin (channel-get nats) (sieve nats)))
 
==== usingUsing generators ====▼
(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)
Line 1,926 ⟶ 1,911:
(define (sieve g)
(generator ()
(let loop ([g g]) (let ([x (g)]) (yield x) (loop (sift x g))))))
(define primes (begin (nats) (sieve nats)))
(for/list ([i 25] [x (in-producer primes)]) x)</lang>
 
(define (take-upto n p)
(let loop ()
(let ([x (p)]) (if (<= x n) (cons x (loop)) '()))))
(take-upto 100 primes)</lang>
 
=={{header|REBOL}}==
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/45960"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information