Problem 7

エラトステネスの篩の限界を見た。

Problem 7 - PukiWiki

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

10001 番目の素数を求めよ。

これは相当キツい。


前に作った奴を利用してっと。

(define (primers n)
  (define (iter l)
    (if (null? l)
        '()
        (cons (car l)
              (iter (filter
                      (lambda (o)
                        (not (zero? (modulo o (car l)))))
                      (cdr l))))))
  (iter (iota (- n 1) 2)))

(list-ref (primers 200000) (- 10001 1))  ; 104743

104761らしい。

  • MzSchemeだと20秒程。
  • GaucheでやったらOSが悲鳴を上げたので中止。

MzSchemeはやっぱすげぇ。僕のおバカプログラムでもちゃんと動く。Gaucheより遥に早い。


おっと、Spaghetti Source - 各種アルゴリズムの C++ による実装にもうちょっと早くなりそうな実装がある。