links

< home >
< unix stuff >
< code >
< writing >
< archive >
< music >
< photos >
< recipes >
< site map >
< about badcomputer >

sieve of eratosthenes

Python

; Sieve of Eratosthenes in Scheme
; Written by Robert Hoelz
;
; Note: I decided to write this in a continuation-based style, which doesn't
; really affect the time/space complexity of the program, but it's cool to
; use continuations. =D
;
; Until I find out a more portable way to run this, this code only truly works
; in mzscheme.  To run, type "mzscheme -i sieve.scm <number>" on the command line.
; If you really want to run the code in a different Scheme environment, such as
; guile, just remove the last line and execute main with a vector, like this:
;
; (main #("100"))

(define (% lhs rhs)
  (- lhs (* rhs (floor (/ lhs rhs)))))

(define (main argv)
  (if (= 0 (vector-length argv))
    '()
    (let ((result #f))
      (begin
        (set! result (call/cc (lambda (k) (generatePrimes (string->number (vector-ref argv 0)) k))))
        (if (cadr result)
          (begin (display (car result)) (display " ") ((cadr result) 0))
          '())
        (newline)))))

(define (generatePrimes limit yield)
  (let ((result (genPrimeLoop (initPrimes limit) limit 2 yield 0)))
    (provideRest (car result) yield (cadr result))))

(define (genPrimeLoop primes limit currPrime yield index)
  (if (<= (* currPrime currPrime) limit)
    (begin
      (call/cc (lambda (k) (yield (list currPrime k))))
      (let ((modPrimes (removeMultiples primes currPrime index)))
        (genPrimeLoop (cdr modPrimes) limit (nextPrime modPrimes (+ currPrime 1) index) yield (+ index 1))))
    (list primes index)))

(define (provideRest primes yield index)
  (if (null? primes)
      (yield (list #f #f))
      (begin
        (if (= (car primes) 1)
          (call/cc (lambda (k) (yield (list index k))))
          '())
        (provideRest (cdr primes) yield (+ index 1)))))

(define (initPrimes limit)
  (if (= limit 1)
    '(0 0)
    (append (initPrimes (- limit 1)) '(1))))

(define (removeMultiples primes base index)
  (if (null? primes)
    '()
    (if (= (car primes) 1)
      (if (= 0 (% index base))
        (cons 0 (removeMultiples (cdr primes) base (+ index 1)))
        (cons 1 (removeMultiples (cdr primes) base (+ index 1))))
      (cons 0 (removeMultiples (cdr primes) base (+ index 1)))
      )))

(define (nextPrime primes currPrime index)
  (if (= currPrime index)
    (if (= (car primes) 1)
      currPrime
      (nextPrime (cdr primes) (+ currPrime 1) (+ index 1)))
    (nextPrime (cdr primes) currPrime (+ index 1))))

(main argv)

back to Eratosthenes page

stats

It is Saturday May 17, 2008 10:53 am
This page served 635 times
This page last modified: April 14, 2008 11:28 am
Your IP address is: 38.103.63.17
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 10:53:54 up 23 days, 11:36, 0 users, load average: 0.00, 0.00, 0.00