Primality by trial division: Difference between revisions
Content deleted Content added
m →Infinite list of primes: Rewritten a bit |
|||
| Line 1,865: | Line 1,865: | ||
=== Infinite list of primes === |
=== Infinite list of primes === |
||
==== |
==== Using laziness ==== |
||
This example uses infinite lists (streams) |
This example uses infinite lists (streams) to implement a sieve algorithm that produces all prime numbers. |
||
<lang Racket>#lang lazy |
<lang Racket>#lang lazy |
||
;; infinite list using lazy racket (see the language above) |
|||
(define nats (cons 1 (map add1 nats))) |
(define nats (cons 1 (map add1 nats))) |
||
(define (sift n l) (filter (λ(x) (not (zero? (modulo x n)))) l)) |
(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 (sieve l) (cons (first l) (sieve (sift (first l) (rest l))))) |
||
(define primes (sieve (rest nats))) |
(define primes (sieve (rest nats))) |
||
| ⚫ | |||
| ⚫ | |||
(define (take-upto n l) |
|||
(if (<= (car l) n) (cons (car l) (take-upto n (cdr l))) '())) |
|||
| ⚫ | |||
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. |
|||
| ⚫ | |||
Same as above. Infinite list using threads and channels (similar to newsqueak). |
|||
<lang Racket>#lang racket |
<lang Racket>#lang racket |
||
| ⚫ | |||
| ⚫ | |||
(syntax-case stx () |
(syntax-case stx () |
||
[(_ expr ...) |
[(_ (name . args) expr ...) |
||
(with-syntax ([out! (datum->syntax stx 'out!)]) |
(with-syntax ([out! (datum->syntax stx 'out!)]) |
||
#'( |
#'(define (name . args) |
||
| ⚫ | |||
(define (out! x) (channel-put out x)) |
(define (out! x) (channel-put out x)) |
||
(thread (λ() (let loop () expr ... (loop)))) |
(thread (λ() (let loop () expr ... (loop)))) |
||
out))])) |
out))])) |
||
(define |
(define-thread-loop (nats) (for ([i (in-naturals 1)]) (out! i))) |
||
(define (filter pred? c) |
(define-thread-loop (filter pred? c) |
||
( |
(let ([x (channel-get c)]) (when (pred? x) (out! x)))) |
||
(define (sift n c) (filter (λ(x) (not (zero? (modulo x n)))) c)) |
|||
(define ( |
(define-thread-loop (sieve c) |
||
( |
(let ([x (channel-get c)]) (out! x) (set! c (sift x c)))) |
||
(define (sieve |
(define primes (let ([ns (nats)]) (channel-get ns) (sieve ns))) |
||
( |
(for/list ([i 25] [x (in-producer (λ() (channel-get primes)))]) x)</lang> |
||
(out! x) |
|||
| ⚫ | |||
(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> |
|||
| ⚫ | |||
Yet another variation of the same algorithm as above, this time using generators. |
Yet another variation of the same algorithm as above, this time using generators. |
||
<lang Racket>#lang racket |
<lang Racket>#lang racket |
||
(require racket/generator) |
(require racket/generator) |
||
(define nats (generator () (for ([i (in-naturals 1)]) (yield i)))) |
(define nats (generator () (for ([i (in-naturals 1)]) (yield i)))) |
||
(define (filter pred g) |
(define (filter pred g) |
||
| Line 1,926: | Line 1,911: | ||
(define (sieve g) |
(define (sieve g) |
||
(generator () |
(generator () |
||
(let loop ([g g]) (let ([x (g)]) (yield x) (loop (sift x g)))))) |
(let loop ([g g]) (let ([x (g)]) (yield x) (loop (sift x g)))))) |
||
(define primes (begin (nats) (sieve nats))) |
(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}}== |
=={{header|REBOL}}== |
||