予備校地理講師兼進学塾講師・山岡信幸のブログです。
昨日の記事 に出てきた「エラトステネスの篩(ふるい)」は素数を探すためのアルゴリズムです。

素数 … 1と自分自身の2つしか約数を持たない(1と自分自身でしか割り切れない)整数。1は含まない。
      整数を積の形で考えるときの「元素」にあたり、無限に存在する。  ex. 2、3、5、7、…53、…2017、…
      ある整数を素数の積の形で表すのが素因数分解。 ex. 9=3^2 1001=7×11×13 2016=2^5×3^2×7
      (3^2は「3の2乗」つまり3×3のこと)

img107.jpg
1) まず、上図のように1以外の正の整数を書き並べる(ここでは6つずつ書き並べたが、そうでなくても構わない)。
2) 最小の素数である「2」を残し、他の2の倍数を消す(図の赤線)。
3) 残りの整数のうち最小の数(この場合は3)は必ず素数なので、
  これを残して他の3の倍数を消す(図の青線)。
4) 以下、これを繰り返す。
  → 3)のあと、残りの整数のうち最小の数(この場合は5。4はすでに消されている)は必ず素数。
    これを残して他の5の倍数をすべて消す(図の緑線)。
5) はじめに書き並べた整数のうち最大の整数をnとし、「nの平方根」以下の整数について上の作業を終えたら、
  消されずに残った数はすべて素数。
  (上図では最大の数54の平方根が約7.34なので、7の倍数を消した(水色)時点で作業終了)
  この場合、54以下の素数は16個、そのうち最大の素数は53であることが分かりました。

たとえば120までの表を作ったとしても、120の平方根は10.9・・・ですから、
7の倍数を消した時点で事実上作業は終わり(8、9、10はすでに2や3の倍数として消されている)、
120以下で最大の素数が113である※と分かります。

※119や117は素数っぽいですが、119=7×17、117=3^2×13

さらに「2」以外の偶数は素数ではありませんから、はじめから奇数だけで表を書くと楽です。
img109.jpg

このテーマについて、高校受験生は以下に紹介する海城高校(2008年)の入試問題で演習しておきましょう。

1からNまでの自然数(正の整数)を次の規則によって順にひとつずつ消す操作を行う。
 ① まず,最初に1を消す。
 ② 素数2を残して,2以外の2の倍数を小さい順にひとつずつすべて消す。
 ③ 素数3を残して,3以外の3の倍数を小さい順にひとつずつすべて消す。
 ④ 残った数について,素数の小さい方から同様の操作を行う。
 ただし,素数とは,1以外の自然数で,1とその数以外には約数をもたない数である。
 たとえば,N=10のとき,素数2,3,5,7が残り,自然数は1,4,6,8,10,9の順で消
す。したがって,最後に消した数は9で6番目に消したことになる。
 次の問いに答えよ。
(1) N=100のとき,最後に消える数は何か。また,それは何番目に消えるか。
(2) Nを100より大きい数としたとき,(1)で求めた最後の数が,最後に消える数ではな
 くなるNの最小値を求めよ。
(3) このように数を消していったところ,221が最後に消える数となるNの最大値を求めよ。


正解は下の方の追記にて。


正解
(1) 100の平方根は10だから、素数7の倍数を消した時点で終了する。
  最後の数は7×13=91
  100以下の素数は25個だから、消された数=非素数は75個。
  よって最後に消された91は75番目
(2) 素数11の倍数を消す必要が出てくるのは、N=121のとき(11は121の平方根)。
  そこで91より大きく121未満の7の倍数を確認すると,
  7×14 7×15 7×16 7×17
  はじめの3つは2や3の倍数として消されてしまうので、
  7の倍数として最後に消されるのは 7×17=119
(3) 221=13×17 は13の倍数として消される。
  13の次の素数17の倍数を消す必要が出てくるのは
  N=289のとき(17は289の平方根)。
  289未満の13の倍数のうち、13未満の素数の倍数でないものは
  13×19=247 
  よってN≧247のときには247が最後に消える数になってしまう。
  よって、N=246までは221が最後に消える数である。
関連記事
スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://geoyamaoka.blog86.fc2.com/tb.php/1596-6127f587
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック