Chat (Lingr.com)
Informaiton
Daily
Column
- MySQL日本語の旅(5/1)
- アクセス向上秘伝(5/9)
- 一風変ったHaskellλ門(6/13)
- SICP Answer Book (5/31) 問題3.26追加
Zope Solution
Extra
アーカイブ
OSS案内所
Site Info
関連リンク
##(link2sicp "book-Z-H-11.html#%_thm_1.24" "Exercise 1.24")
解答例
Fermatテストはθ(log n)の増加なので、1,000,000近傍の素数をテストする時間は 1,000近傍の素数をテストする時間の2倍程度になると予想できる。
実行結果
gosh> (search-for-primes 1000 3) 1001 1003 1005 1007 1009 *** #<time-duration 0.000506000> 1011 1013 *** #<time-duration 0.000517000> 1015 1017 1019 *** #<time-duration 0.000543000> done gosh> (search-for-primes 10000 3) 10001 10003 10005 10007 *** #<time-duration 0.000646000> 10009 *** #<time-duration 0.000615000> 10011 10013 10015 10017 10019 10021 10023 10025 10027 10029 10031 10033 10035 10037 *** #<time-duration 0.000646000> done gosh> (search-for-primes 100000 3) 100001 100003 *** #<time-duration 0.001171000> 100005 100007 100009 100011 100013 100015 100017 100019 *** #<time-duration 0.001176000> 100021 100023 100025 100027 100029 100031 100033 100035 100037 100039 100041 100043 *** #<time-duration 0.001192000> done gosh> (search-for-primes 1000000 3) 1000001 1000003 *** #<time-duration 0.001545000> 1000005 1000007 1000009 1000011 1000013 1000015 1000017 1000019 1000021 1000023 1000025 1000027 1000029 1000031 1000033 *** #<time-duration 0.001561000> 1000035 1000037 *** #<time-duration 0.001574000> done
実験では、以上のように、2倍ではなく、3倍程度になっている。 現在のところ筆者はこの理由を説明できません。
わかる方、教えてくださいませ。
コード
##(sicp-answer-code "ex-1.24.scm")
