前回まで素数の必要性を話していきましたが、そうしたらどうやって素数ってみつけていくのっていう話です。
素数とは、１より大きい自然数で、さらに約数がその数自身と１の２つしかないという数のことでしたよね。
では、素数を探す手順を紹介します。
2以外は奇数だけを考える。
１は約数が１つしかないので、2以上を考えるのですが、偶数は絶対に2を約数にもつので、2以外は奇数だけを考えます。
奇数の約数は奇数しかない
奇数の約数に偶数をもつことはないので、奇数の約数が存在するかを確認していけばよいのです。
その数の半分の数まで探せばよい。
例えば、69は素数かどうかを考えるとき、1と67以外に約数を持つかということを考えます。
小さい順から考えると、
$69 \div 2 = 34 \mbox{余り1}$ ・・・ 2は約数でない
$69 \div 3 = 23$ ・・・ 3は約数である。
・
・
・
ということがわかります。
ここで、3が約数ということであれば、23も約数であるということがわかります。
つまり69の半数までかぞえれば、残りの半数に約数が存在するか否かは断定できるのです。
コードにしてみる
def sosu(num): if num < 2: # 2以上の自然数対象 return False elif num == 2: # 2は素数 return True elif num % 2 == 0: # 2以外の偶数は素数でない return False else: # 奇数は１とその数と自身以外に約数があれば約数でない for i in range(3, num // 2, 2): if num % i == 0: return False else: return True # 100未満の素数を探索する for i in range(100): if sosu(i): print(i) -> 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
→
