素数判定は、半分まで確認すればいい？

先日、Excelで素数判定する機会があった。
このテーマについて、改めて考えてみた。

Wikipediaによれば、素数の定義は以下のとおり。

素数（そすう、英: prime number）とは、1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののことである。

従って１から自分自身の数までで順に割っていき、途中に割り切れるものがあれば、それは素数ではない。

例えば「10」の場合、途中「5」で割り切れるため素数ではない。

一方で「11」の場合、「11」で二回目に割り切れるため、素数となる。

しかし、11の場合に11まで確認する必要があるか？と考えると、そうでもない。
なぜなら半分以上の数、11で言えば6以上の数で割った値は必ず２未満となる。

従って、その値の半分まで約数が登場しなければ、
それは素数と言えないだろうか。

以上を踏まえ作成したのが、こちら。

Function 素数判定(num As Long) As Boolean
    Dim i As Long
        If num <= 1 Then
            素数判定 = False
        ElseIf num = 2 Then
            素数判定 = True
        Else
            For i = 2 To WorksheetFunction.RoundUp(num / 2, 0)
                If num Mod i = 0 Then
                    素数判定 = False
                    Exit Function
                End If
            Next
            素数判定 = True
        End If
End Function

あくまで「数多くある方法の中の一つ」ということで。

参考まで。