素数っていくつあるの？｜もちのき研究所

こんにちは、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

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

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

定理1の証明

素数が有限個であると仮定します。
その個数をnとして、素数を $p_1,p_2,\ldots,p_n$ とします。
この時、 $p = p_1 p_2 \cdots p_n +1$ を考えます。
pは仮定より $p_1,p_2,\ldots,p_n$ のどれかで割り切れなければなりません。
しかし、どの素数で割っても1が余ります。
よって、pは素数になり、かつ $p>p_i \ (i=1,2,\ldots,n)$ です。
これは矛盾です。
従って、素数は無限個あります。

命題「 $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以下の素数を列挙できました。