素数判定プログラム
あると便利なプログラム。ここでは少しだけ素数の性質を利用したアルゴリズムを説明する。
シンプルな素数判定
素数の定義から、
ということがわかる。これをそのままプログラムにすれば、素数は判定できる。
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の約数が存在しているということになる。
変更後プログラム
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
これだけでも、だいぶ早くなる。