数学

素数っていくつあるの?

こんにちは、MSKです。
今日は数学の話の中でも興味を持つ人が多い素数について、その個数のお話をします。

そもそも素数とは?

素数を定義します。
素数とは1と自分自身以外に割り切れない数字のことを言います。

数学的にちゃんと定義をすると、

定義(素数)

p \in \mathbb{N}でp>1とします。
pが素数 \overset{\text{def}}{\Longleftrightarrow} \forall x, y \in \mathbb{N} (p = xy \Rightarrow x = 1 \lor x = p)

素数でない正の整数を合成数といいます。

となります。

素数の例としては2,3,5,7,11などです。
どれも1と自分自身でしか割り切れません。

素数は何個あるの?

ずばり答えを言うと、無限個あります!

定理1

素数は無限個に多く存在します。

証明は簡単です。
素数が有限個と仮定して、矛盾を導きます。

命題「p_1,p_2,\ldots,p_nが素数 \Rightarrow p = p_1 p_2 \cdots p_n +1は素数である」は真ではありません。
上の証明では「素数が有限個」という仮定の下で存在する全ての素数の積を取っていることで成り立っています。

ちなみに反例は簡単に作れます。
2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 39 \times 509

ちなみにですが、現時点で知られている最大の素数は2^{82589933} − 1です。
これは51番目の知られているメルセンヌ素数で、2486万2048桁の数字です。

素数を並べてみよう

すべての素数を出すことは不可能なので、いくつか素数を並べてみたいと思います。
Pythonを使って素数を表示します。

import sys

args = sys.argv

def enum_prime_number(max_value):
    prime_number_list = [2] #2は最初から素数にいれておく
    for target_number in range(2,max_value): 
        is_composite_number=False #合成数かチェックするため
        for listed_prime in prime_number_list: #今まで列挙している素数で割る
            if target_number % listed_prime == 0: #余りが0なら割りきれているので合成数
                is_composite_number = True
                break
        if is_composite_number == False: #今まで列挙している素数で割れないなら新しい素数
            prime_number_list.append(target_number)
    return prime_number_list

if __name__ == "__main__":
    max = 100
    pl = enum_prime_number(max)
    print(pl)

結果は以下のようになります。
[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]

ちゃんと100以下の素数を列挙できました。

まとめ

素数が無限個あることを紹介しました。
素数は数学者にとって惹きつけられる対象です。
素数の面白い話があったら、今後も紹介していきたいと思います。

以上、「素数っていくつあるの?」でした。
最後までご覧いただき、ありがとうございました。

ABOUT ME
MSK
九州在住の組み込み系エンジニアです。 2児の父親でもあります。 数学やプログラミングが趣味です。 最近Webプログラミングと曲面結び目理論にはまっています。