<i> <small> <a href="http://www.aichi-edu.ac.jp/" target="_top">愛知教育大学</a> > <a href="http://www.auehs.aichi-edu.ac.jp/" target="_top">附属高校</a> > <a href="http://www.auehs.aichi-edu.ac.jp/ko-cho-aisatu/ko-cho.html" target="right">校長室</a> > <a href="http://133.96.66.29/challenge/" target="right">附高生にチャレンジ</a> </small> </i> **38(7/10):1000000以下の素数の個数を短時間で調べるには？ ? - 大学院生としての天羽先生と,いろいろなプログラミングをしています。 - アルゴリズム(計算の仕方)を工夫することで, 計算スピードはとても変わります。 - その一例として, 「素数を調べる」課題を考えてみましょう。 - 素数とは, 「1と自分以外に約数がない」ものをいいますから, -- 「整数nに対して1からnまで調べたとき, 割り切れる(約数になる)ものが2個」(*) -という判定の仕方をするプログラムが基本になります。 - この計算方法で, 1000以下の素数の個数を調べると, 0.46秒かかりました。 - (1) この計算方法で, 10000以下の素数の個数を調べるには, 約何秒かかると思いますか? -- ... -- (実際には, 約48秒かかりました。) - (2) この計算方法で, 100000以下の素数の個数を調べるには, 約何秒かかると思いますか? -- 上記を実際に確かめようとしたら, 「ほぼ止まったまま」。仕方がないので, 20000以下について調べてみたところ, 次のように, 約3分15秒かかりました。 -- さらに, 1000000以下の素数の個数を調べるとしたら, どれくらいの時間がかかると思いますか。 - (3) 天羽先生は, (*)の改良版をつくってくれました。 - 改良版を使った結果を調べてみると, 次のようになります。 -- 1000以下 : 0.048 (*の方法の 0.1倍の時間) -- 10000以下 : 0.13秒 (*の方法の 0.003倍の時間) -- 20000以下 : 0.26秒 (*の方法の 0.0013倍の時間) -- 100000以下 : 1.73秒 -- 1000000以下 : 36.5秒 -- 個数が増えていくほど, 天羽先生のアルゴリズムのよさが実感できますね。 - 天羽先生の方法でいけば, たとえば, 24時間かけるといくつまでの素数の個数を調べることができると思いますか? - (4) 方法(*)と比較すると, 天羽先生の方法はとてもすばらしいと思うのですが, 一体どういう考え方に基づくものでしょうか。ぜひ考えてみてください。(もしかすると, もっといい方法もみつかるかもしれませんね。) ?? -備考 -- 下記が, 今回使ったプログラム例です。(Pythonというプログラミング言語を使っています) <pre> def num_primes(n): n_p=0 for k in range(2,n+1): if isPrime(k) : n_p=n_p+1 print(n, " : ", n_p) def isPrime(n): num_yakusuu=0 for i in range(1,n+1): if n % i == 0 : num_yakusuu = num_yakusuu + 1 if num_yakusuu==2: return True else: return False num_primes(10000) </pre>