素数判定プログラム

あると便利なプログラム。ここでは少しだけ素数の性質を利用したアルゴリズムを説明する。

素数とは

素数とは、1とその数自身でしか割り切れない数。例えば、2は素数。なぜなら、1と2でしか割れないからである。でも、1は素数ではない。

シンプルな素数判定

素数の定義から、

  • 0と1は非素数である。
  • 2〜n-1までの数にnを割り切る数がなければ、nは素数

ということがわかる。これをそのままプログラムにすれば、素数は判定できる。

def prime(n):
	i=2
	if n==1 or n==0: return 0
	while i<n:	#2〜n-1まで
		if n%i==0:
			return 0
		i+=1
	return 1

この関数primeにnを与えれば、素数なら1、非素数なら0を返す。

メモ

当初、rangeを使って繰り返しをしていたが、数値が大きいときにエラーを起こした。whileにすると解消された。

もう少し、効率的に

上のプログラムは単純労働の力技。すなわち、しらみつぶしというやつで、全部の可能性を検証して素数だと初めてわかるプログラムである。ある1つの数についての検証ならともかく、素数のようにランダムに存在する数を探すならば大変である。

割る範囲は2〜√nまででよい

例えば、n=i*jという式で表されたとすると、iかjは必ず√n以下になる。なぜなら、i=j=√nのときにnになるから。
すなわちnが素数でなければ、√n以下の数にnの約数が存在しているということになる。

素数は奇数である

2以外の素数は必ず奇数である。なぜなら、偶数なら2で割れるから。なので、偶数を検証する必要はない。

変更後プログラム
import math
def prime2(n):
	i=3
	if n==1 or n==0: return 0
	if n%2==0: return 0 #偶数なら非素数
	while i<math.sqrt(n):	#3〜√nまで
		if n%i==0:
			return 0
		i+=1
	return 1

これだけでも、だいぶ早くなる。