中学の数学 (8) 素数を python で探そう

Kimono club

2024年4月14日 22:14

[ サイトマップを見る ]

素数

今日学ぶこと

数をみたら，それが素数かどうか判定できる

ある数 n があるとしましょう。n の約数が2個しかない場合，n は素数です。

約数が2個しかない場合というのは，具体的には 1 と n の2個しかない場合です。

式で理解する

式で書いたほうがわかりやすいかな。n が素数の場合，約数は 1 と n のふたつであることを次の式はあらわしています。

$${ n = 1 \times n }$$

具体例で理解する

具体的な数字を使って見ていきましょう。

$${ 2 = 1 \times 2 }$$

約数は2個しかないので，2 は素数です。

$${ 3 = 1 \times 3}$$

3も約数は2個しかないので，3は素数です。

$${4 = 1 \times 2 \times 2}$$

4は約数が3個あります。4は素数ではありません。

$${5 = 1 \times 5}$$

5は約数が2個です。5は素数です。

演習問題

それではここで演習をしましょう。まず，これまで学んだことの復習です，

素数とは，約数が2個の数のことをいいます。いいですか？約数が2個の数，具体的には１と自分自身を約数とするような数のことです。

演習１　1 は素数ですか？
演習２　6 は素数ですか？

演習の答え
演習１　1 は素数ではありません。なぜなら，1 の約数は 1，一つしかないからです。素数の定義では約数が2個の数を素数といいますから，1は素数ではありません。

演習２　6は素数ではありません。

$${6 = 1 \times 2 \times 3}$$

python で素数を探そう

以前，約数を探すコードを Python で書きました。

import math 

def divisors(n): 
    l = [] 
    l.append(1) 
    for i in range(2, math.floor(n/2)+1): 
        if n % i == 0: 
            l.append(i) 
    l.append(n) 
    return(l) 

l = [] 
l = divisors(100) 
print(l)

リスト l のなかに約数がはいっています。

このコードを修正して，ある数が素数がどうかを判定するコードを書きましょう。
まず素数というのは約数が２つしかない数をいいます。リスト l のなかに２つだけ約数があれば，それは素数ですね。

リストの数は関数 len() で数えることができます。len という名前は，length，長さという英単語からきています。

import math 

def is_prime_number(n): 
    l = []
    l.append(1) 
    for i in range(2, math.floor(n/2)+1): 
        if n % i == 0: 
            l.append(i) 
    l.append(n) 
    return(len(l) == 2) 

n=100
print(n, end="")
print(" is ", end="")
if is_prime_number(n) == False:
    print("NOT ", end="")
print("a prime number.")

関数の最後の行に次のような記述があります。

    return(len(l) == 2)

len(l) でリスト l に何個数字が入っているか調べています。それが 2 かどうか，２であれば True，2でなければ False となります。それを戻り値として返しています。素数であれば，True, 素数でなければ，False が帰ってくるわけですね。

それでは次に2 から　1000 までの素数を書き出すコードを書いてみましょう。

import math 

def is_prime_number(n): 
    l = []
    l.append(1) 
    for i in range(2, math.floor(n/2)+1): 
        if n % i == 0: 
            l.append(i) 
    l.append(n) 
    return(len(l) == 2) 

l = []
for i in range(2,1001):
    if is_prime_number(i):
        l.append(i)
print(l)

実行すると，以下のように出力されます。

[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

1000まででしたら，ほとんど実行に時間はかかりません。10000までも，ほとんど時間はかからないでしょう。しかし，100000 以上になると，ちょっと待たないと計算が終わりません。

コードの無駄を取り除けば，もっと計算ははやくなります。また，別の記事で計算量を小さくすることに挑戦してみましょう。