Chapter 07

Problem 7: 10001st prime

aoi.iter
aoi.iter
2022.06.24に更新
このチャプターの目次

2022/06/24

https://projecteuler.net/problem=7

問題

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

10001 番目の素数を求めよ.

考察

方針

  • 素数リストを生成するためのアリストテレスの篩は 1~N のうちの素数をフィルタするのに使えるが、Hoge 番目の素数の特定をしようとすると実装がめんどくさい
  • 素直に試し割り法が良さそう

実装

  • 既知の素数リストを作っておく(最初は 2 のみ)
  • 素数リストの生成関数を作成する
    • 対象の数値 N と既知の素数リストを引数にとり、素数リストのうち\sqrt{N} 以下のもので N が割り切れるかどうか判定する
    • 割り切れるものであれば無視して(N+1)のための処理を開始する
    • 割り切れないものであれば素数リストに追加したうえで(N+1)のための処理を開始する
    • 以上の処理を N について 2 から行う

解答

; https://projecteuler.net/problem=7
(use gauche.generator)


(define (prime? n primes)
  (every (lambda (p) (not (zero? (mod n p))))
         (filter (lambda (p) (<= (square p) n))
                 primes)))

(prime? 3 '(2))
; => #t

(define (make-prime-generator)
  (generate (lambda [yield]
              (let loop ([n 2] [prime-list '(2)])
                (if (prime? n prime-list)
                    (begin (yield n)
                           (loop (+ n 1) (cons n prime-list)))
                    (loop (+ n 1) prime-list))))))

(define (generator-index g idx)
  (car (generator->list
        (gtake (gdrop g idx) 1))))

(generator->list (gtake (make-prime-generator) 6))
; => (2 3 5 7 11 13)
(generator-index (make-prime-generator) 5)
; => 13
(generator-index (make-prime-generator) 10000)
; => 104743

感想

generatorに初挑戦した

https://practical-scheme.net/gauche/man/gauche-refj/zienereta.html#index-gauche_002egenerator
generate項にある^(カレット)の意味がわからず困惑したが、lambda

参考資料

N/A