2以上の自然数$N}$が素数かどうかを判定する方法 以下のすべての素数で割り切れない}ならば,\
自然数Nの約数には対称性がある}のであった.
例えば,\ 36の約数は\ 1,\ 2,\ 3,\ 4,\ 6,\ 9,\ 12,\ 18,\ 36である.
このとき,\ 1･36=2･18=3･12=4･9=6^2=36となっている.
よって,\ 36がもつ素因数を探すとき,\ 対称中心6より大きな数で割り切れるかを考える必要はない.
さらに,\ 4のような合成数で割り切れるかを考える必要もない.
4で割り切れるならば,\ 4がもつ素因数2でも割り切れるはずだからである.
結局,\ √{36}=6以下の素数で割り切れるか否かにより,\ 36が素数か否かを判定できる}わけである.
一般化すると( A)となる.\ 以下に証明を簡潔に示す.\ \ N≠1とする(1は素数でも合成数でもない).
対偶「Nが素数でない(合成数)ならば,\ √ N\,以下の少なくとも1つの素数で割り切れる」
}\ \ これを背理法で示す.
}\ \ Nが合成数であるとき,\ Nは少なくとも2つの素因数p,\ q\ (pq≦ N)をもつ.
}\ \ p>√ N\ かつ\ q>√ N\ と仮定すると
エラトステネスのふるい
古代ギリシャの学者エラトステネスが考案した素数判定法を紹介する.
任意の自然数$N}$以下のすべての素数をあぶり出すアルゴリズムである.
[1]\ \ 1は素数ではないので消す.
[2]\ \ 残る自然数のうち最小の数に○をして,\ その倍数をすべて消す(ふるい落とす).
[3]\ \ [2]\,を繰り返し,\ 最小の数が$√ N}$を超えたところで終了.\ 残った数が素数である.
N=50の例を示した.\ まず1を消去,\ 2に○をして,\ 2の倍数をすべて消す.
10個ずつ並べた自然数の表ならば,\ 偶数が縦に並ぶので縦線で一気に消せばよい.
次に,\ 残る自然数のうち最小の数3に○をして,\ 3の倍数をすべて消す.
10個ずつ並べた自然数の表ならば,\ 3の倍数が斜めに並ぶので斜め線で一気に消せばよい.
√{50}<√{121}=11\ より,\ 同様の処理は7までで終了である.
残ったすべての数が素数である.\ わかりやすいように残った数にも○をしておいた.
2021は素数か.
一の位は1なので2,\ 5の倍数ではない.
$2+0+2+1=5$より,\ 3の倍数ではない.
$44^2=1936,\ 45^2=2025$\ より $44<√{2021}<45}$
44以下の2,\ 3,\ 5を除く素数で実際に割り切れるかを試していくと,\ 43で割り切れる.
$2021=43×47}$より,\ 素数ではない.
$2021=2025-4=45^2-2^2}=(45+2)(45-2)=47･43}$\ より,\ 素数ではない.
2021=43･47さえ書いてあれば答案として十分だが,\ ここでは思考手順も示した.
まず,\ 2,\ 5,\ 3の倍数条件を満たすかを確認する.
3の倍数条件は,\ 各位の和が3の倍数}であった.
2,\ 3,\ 5で割り切れなければ,\ 後は小さい素数から順に割り切れるかを試していくしかない.
あらかじめ√{2021}\,を不等式で評価}し,\ どの素数まで考慮する必要があるかを確認しておく.
40^2=1600,\ 50^2=2500より,\ 試しに45^2\,を計算すると√{2021}=44.･･･\ と予想できる.
結局本問の場合,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43をすべて試すことになる.
a^2-b^2\,の形で表せるという2021がもつ特殊性}に気付ければ,\ 素早く素因数分解できる(別解).
高校数学では,\ 時々\,√{n}\,を評価すべき状況に出くわす.
このとき,\ A5^2\,の値を瞬時に求める計算の裏技を知っていると素早くアタリをつけることができる.
一般に,\ A5^2\,の値は,\ 上2桁はA(A+1),\ 下2桁は必ず25}となる.
(10A+5)^2=100A^2+100A+25=A(A+1)･100+25だからである.
例えば,\ 45^2=[\,4(4+1)\,|\,25\,]=2025,\ \ 105^2=[\,10(10+1)\,|\,25\,]=11025\ などとなる.
√ n\,の評価以外にもA5^2\,を計算する機会は多く,\ 非常に有用な裏技である.
普段からこの裏技に慣れていると,\ 2021=45^2-2^2\,のような変形にも気付きやすくなる.
1000以下の素数は250個以下であることを示せ. [\,一橋大\,]
言うまでもなく,\ 試験時間中に素数をすべて書き出す方針は現実的ではない.
仮に書き出せたとしても,\ それ以外に素数がないことが示されていなければ答案として不十分である.
結局,\ 明確に判定できる素数でない数が750個以上あることを示す}ことになる.
まず,\ 個数が多い2,\ 3,\ 5の倍数の個数を数える.
3つの集合の和集合A∪ B∪ Cは,\ 重複に注意し,\ 以下のようにして求めるのであった.
(2または3または5)=(2)+(3)+(5)-(2かつ3)-(3かつ5)-(5かつ2)+(2かつ3かつ5)
250個という問題設定が絶妙で,\ 2,\ 3,\ 5の倍数だけでは750個に届かないのが本問の肝である.
しかも,\ 2,\ 3,\ 5が素数トラップ}に注意しなければならない.
素数でないものが2,\ 3,\ 5の倍数以外に19個あることを示す必要が生じる.
つまり,\ 2,\ 3,\ 5以外の素数の積で表される合成数}を書き出すことになる.
このような合成数で最も単純なのは(素数)^2\,であり,\ 1000以下となるのは31^2=961までである.
ついでに素数でも合成数でもない1}も加えておく.
後は適当に10個書き出せばよい.\ ここでは7･(素数)を書き出したが,\ 当然11･13などでもよい.
ちなみに,\ 実際には1000以下の素数は168個ある.
参考までに,\ オイラー関数\,\phi(n)\ (後に詳しく紹介する裏技)を利用する別解を示しておく.
\phi(n)は,\ n以下でnと互いに素(最大公約数1)である自然数の個数を表す.
nがn=p^aq^br^cs^d\,と素因数分解できるとき
素数ならば,\ 少なくとも2,\ 3,\ 5,\ 7と互いに素でなければならない.
1050以下で1050=2･3･5^2･7,\ つまり2,\ 3,\ 5,\ 7と互いに素な自然数の個数は
これに2,\ 3,\ 5,\ 7の4個を加えた244個が素数の可能性がある数である.
つまり,\ 素数の可能性がある数は,\ 1050までであっても最大で244個しかない.
すなわち,\ 1000以下の素数は250個以下である.
