[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/1pbA8QjE    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Apr 14:
; twin primes

; primes n -- list of primes not greater than n in ascending order
(define (primes n) ; assumes n is an integer greater than one
  (let* ((len (quotient (- n 1) 2)) (bits (make-vector len #t)))
    (let loop ((i 0) (p 3) (ps (list 2))) ; sieve of eratosthenes
      (cond ((< n (* p p))
              (do ((i i (+ i 1)) (p p (+ p 2))
                   (ps ps (if (vector-ref bits i) (cons p ps) ps)))
                  ((= i len) (reverse ps))))
            ((vector-ref bits i)
              (do ((j (+ (* 2 i i) (* 6 i) 3) (+ j p)))
                  ((<= len j) (loop (+ i 1) (+ p 2) (cons p ps)))
                (vector-set! bits j #f)))
            (else (loop (+ i 1) (+ p 2) ps))))))

; inverse x n -- modular inverse: y such that x*y == 1 (mod n)
(define (inverse x n)
  (let loop ((x (modulo x n)) (a 1))
    (cond ((zero? x) (error 'inverse "division by zero"))
          ((= x 1) a)
          (else (let ((q (- (quotient n x))))
                  (loop (+ n (* q x)) (modulo (* q a) n)))))))

(define (twins n)
  (let* ((len (ceiling (/ n 6)))
         (b1 (make-vector len #t))
         (b2 (make-vector len #t))
         (ps (cddr (primes (inexact->exact (ceiling (sqrt n)))))))
    (do ((ps ps (cdr ps))) ((null? ps))
      (let ((x (inverse 6 (car ps))))
        (do ((i (+ x -1 (if (= (car ps) (- (* 6 x) 1)) (car ps) 0))
                (+ i (car ps))))
            ((<= len i))
          (vector-set! b1 i #f)))
      (let ((x (inverse -6 (car ps))))
        (do ((j (+ x -1 (if (= (car ps) (+ (* 6 x) 1)) (car ps) 0))
                (+ j (car ps))))
            ((<= len j))
          (vector-set! b2 j #f))))
    (let loop ((k 0) (ts (list 4)))
      (if (= len k) (reverse ts)
        (loop (+ k 1)
              (if (and (vector-ref b1 k)
                       (vector-ref b2 k))
                  (cons (* 6 (+ k 1)) ts)
                  ts))))))

(display (twins 1000)) (newline)
(display (length (twins 1000000))) (newline)


Output:
1
2
(4 6 12 18 30 42 60 72 102 108 138 150 180 192 198 228 240 270 282 312 348 420 432 462 522 570 600 618 642 660 810 822 828 858 882)
8169


Create a new paste based on this one


Comments: