試し割り法
From Wikipedia, the free encyclopedia
与えられた整数 n (n はこれから素因数分解する整数）に対して、nより小さい数で割り切れるかどうかを順番に確かめることで素数判定を行う。nが2で割り切れる確率は、nが3で割り切れる確率より高いため、小さい数から順に素因数の候補として割り切れるかを確かめると効率的である。また、nが2で割り切れない場合には4で割り切れないことは明らかであるため、4で割り切れるかを確かめる必要はない。同様に、既に確かめた数の倍数について確かめる必要はないため、素因数候補として確かめる数を素数のみとすることで、労力を削減できる。また、nが何らかの数pで割り切れる場合、n=pqであり、qがpより小さい場合には既にqもしくはqの約数で確かめた際に素因数が検出されているはずである。したがって、素因数候補として確かめるべきはまでで十分ある。
試すべき素因数の個数の上限は簡単に求められる。Pi をi番目の素数とすると、P1=2, P2=3, P3=5……となる。次に、最も運が悪い場合でも、Pi+12>nを満たすPiまで確かめれば良い。また、Piまで試すことでPi+12未満のnまでの判定が可能である。したがって、2と3と5で確かめればn=48（25ではない）の判定が終了する。そして、次の素数7の平方である49からは7で確かめる必要があり（実際49は7×7である）、25未満までであれば2と3のみを確かめれば十分である。nの平方根が整数であればそれは約数であり、nは平方数である。
以下に、篩法を用いて素数を生成する試し割り法のPythonコードを示す。
def trial_division(n):
"""Return a list of the prime factors for a natural number."""
if n < 2:
return []
prime_factors = []
for p in prime_sieve(int(n**0.5)):
if p*p > n: break
while n % p == 0:
prime_factors.append(p)
n //= p
if n > 1:
prime_factors.append(n)
return prime_factors
試し割り法はnが取りうる全ての素因数候補をチェックするため、確実にnの約数を見つけることができる。したがって、もし試し割り法でnの素因数が見つからなければ、nが素数であることの証明になる。逆に、もしnの約数を見つけた場合には、nは確実に合成数である。効率的に言えば、もしその平方がnを超えない素数のいずれかがnを割り切った場合、nは合成数であると判定できる。
