fork(1) download
copy 
  1. ; semi-primes
  2.  
  3. (define (primes n) ; list of primes not exceeding n
  4.   (let* ((len (quotient (- n 1) 2)) (bits (make-vector len #t)))
  5.     (let loop ((i 0) (p 3) (ps (list 2)))
  6.       (cond ((< n (* p p))
  7.               (do ((i i (+ i 1)) (p p (+ p 2))
  8.                    (ps ps (if (vector-ref bits i) (cons p ps) ps)))
  9.                   ((= i len) (reverse ps))))
  10.             ((vector-ref bits i)
  11.               (do ((j (+ (* 2 i i) (* 6 i) 3) (+ j p)))
  12.                   ((<= len j) (loop (+ i 1) (+ p 2) (cons p ps)))
  13.                 (vector-set! bits j #f)))
  14.             (else (loop (+ i 1) (+ p 2) ps))))))
  15.  
  16. (define (semi-primes n)
  17.   (let ((ps (primes (quotient n 2))))
  18.     (let loop ((ps ps) (qs (cdr ps)) (ss (list)))
  19.       (cond ((< n (* (car ps) (cadr ps))) (sort ss <))
  20.             ((or (null? qs) (< n (* (car ps) (car qs))))
  21.               (loop (cdr ps) (cddr ps) ss))
  22.             (else (loop ps (cdr qs) (cons (* (car ps) (car qs)) ss)))))))
  23.  
  24. (do ((k 1 (+ k 1))) ((= k 8))
  25.   (display k) (display #\tab)
  26.   (display (length (semi-primes (expt 10 k))))
  27.   (newline))
Success #stdin #stdout 7.84s 264032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1	2
2	30
3	288
4	2600
5	23313
6	209867
7	1903878
https://ideone.com/jH2sF6
language:
Scheme (chicken 4.13)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!