10001番目の素数

Scheme 30分プログラム

30分プログラム、その266。10001番目の素数 via Project Euler - PukiWiki。

素数を小さい方から6つ並べると2,3,5,7,11,13であり、6番目の素数は13である。
10001 番目の素数を求めよ。

できませんでした。コードは書いたけど、全然計算が終了しない。

せっかくutil.streamの遅延リストを使うチェンスだと思ったのに。

使い方

$time gosh problem7.scm
^C
Received too many signals before processing them.  Exitting for the emergency...
gosh problem7.scm  313.91s user 11.26s system 80% cpu 6:45.91 total

ソースコード

#! /opt/local/bin/gosh
;; -*- mode:scheme; coding:utf-8 -*-
;;
;; problem7.scm -
;;
;; Copyright(C) 2008 by mzp
;; Author: MIZUNO Hiroki / mzpppp at gmail dot com
;; http://howdyworld.org
;;
;; Timestamp: 2008/03/19 22:50:09
;;
;; This program is free software; you can redistribute it and/or
;; modify it under MIT Lincence.
;;
(use util.stream)

(define (sieve xs)
  (let1 x (stream-car xs)
    (stream-cons x
		 (sieve (stream-filter 
			 (lambda (n) (not (= (modulo n x) 0)))
			 (stream-cdr xs))))))

(define prime (sieve (stream-iota -1 2)))
(define (main _)
  (print (stream-ref prime 10000)))

参考