1. この記事は何？
アルゴ式の整数論的アルゴリズムの問題が一通り解き終わったので、忘備録として基本的な中身をまとめておこうと思います。
本当にアルゴリズムとその実装コードをさらっとまとめて、ときたま自分の失敗例を振り返る結構個人的なものなので、もしちゃんとアルゴリズムを勉強したいという方はアルゴ式に取り組まれることをお勧めします。
2. 素数判定法
素数はご存じの通り、1とその数以外では割り切れない数のことです。
整数Nが素数かどうかは、√Nまでの数で割り切れるかどうかを判定すればよいです。
仮にN回計算がかかる処理があったとして、それが√N回の処理で十分なのか、N回すべての計算をしなければならないのかで、両者の計算量はかなり変わってきます。
N=10000のとき、そのままであれば一万回分処理をしなければなりませんが、√Nでいいのであれば僅か100回で計算結果が出ます。
グラフで見ると、よりその差が如実に分かります。
※素数判定法の場合、厳密にN、√N回の計算量があるわけではありません。厳密な計算量で言うと、素数の場合2からN-1まで回して合成数の場合1以外の最小の約数が出た時点で打ち止める最大N-2回の処理と、素数の場合2から√N-1まで回して合成数の場合1以外且つ√N未満の最小の約数が出た時点で打ち止める最大√N-2回の処理があるので、きれいにN、√Nの計算量になるわけではありません。
だいたいの計算量を見積もるという意味では、O(N)、O(√N)という表現が適切です。
以下がそのコードです
def is_prime(num:int) -> bool:
if num <= 1:
return False
else:
for i in range(2,num+1):
if i*i > num:
break
if num % i == 0:
return False
return True
この素数判定のコーディングは少し変更するだけで、約数をすべて書き出すコードにもなります。
def divisor_list(num:int) -> list[int]:
divisor_list = []
for i in range(1, num+1):
if i*i > num:
break
elif i*i == num:
divisor_list.append(i)
else:
if num % i == 0:
divisor_list.append(i)
divisor_list.append(num//i)
return sorted(divisor_list)
O(√N)の計算量を維持しつつ約数をすべて書き出すためには、Nをiで割った値を同時に配列に加えることで可能になります。
3. エラトステネスの篩
ある数までの素数をすべて判定するアルゴリズムです。
さきほどの素数判定のアルゴリズムをそのまま使うと、計算量は $O(N^{3/2})$ になるので、かなり時間がかかることがわかります。
エラトステネスの篩では、まず2からNまでの全ての整数を素数とみなして、ある数が素数であった場合はその倍数すべてから素数のラベルをはがし、Nにいたるまでに素数のラベルが張られたままの数をすべて素数とみなすようなアルゴリズムのことです。
計算量は、2の倍数から素数のラベルをはがす処理こそN/2ですが、次はN/3、N/5となり、どんどん少なくなっていきます。
pを素数とすると、$\sum_{p\leqq N} \frac{N}{p}$ となります。
$\sum_{p} \frac{1}{p}$ の計算量は$O(loglogN)$ になることが知られていますので、これにNをかけて計算量は$O(N \times loglogN)$ となります。
以下がその実装のコードになります。
def sieve_of_eratosthenes(num: int) -> list[int]:
prime_list = [True]*(num+1)
prime_list[0],prime_list[1] = False, False
for i in range(2, num+1):
if prime_list[i]:
j = i * 2
while j <= num:
prime_list[j] = False
j += i
return [j for j in range(num+1) if prime_list[j]]
4. 素因数分解
合成数は素数の積の形に分解することができます。
この実装は自力で組み立てようとしたので思い入れがあります。
ただ、かなり冗長になって分かりにくい失敗例の紹介ですので、興味が無かったら飛ばしてください。
def factorization(N:int) -> dict[int:int]:
factor_in_num = {}
while True:
flag = True
for i in range(2,N+1):
if i*i > N:
if N in factor_in_num:
factor_in_num[N] +=1
else:
factor_in_num[N] = 1
break
if N % i == 0:
flag = False
if i in factor_in_num:
factor_in_num[i] += 1
else:
factor_in_num[i] = 1
N = N // i
break
if flag:
break
return factor_in_num
2からカウントし、Nをiで割り切れる場合、Nとiの商をNとします。for文はNが変わろうがそのままループを続けるので、割り切れる数があった場合は連想配列に素数を追加して抜け出し、while文の中で再度始めからfor文のループを始めます。
もし割り切るものがなかった場合、そのときのNは素数であるということですので、これも素数として連想配列に加えます。また、このときflagは変更されずTrueのままになっているので、whileループが終わります。
素数を連想配列に追加するときは、その素数が連想配列にあったらカウントを増やし、なければ新しく追加するようにしています。
これの問題は、冗長で分かりにくいほかに、while Trueを使っていて実装を間違えれば無限ループのリスクがあることや、わざわざforループ自体を2から何度も繰り返していることも効率的ではありませんでした。
模範解答は以下の通りでした。
def prime_factorize(N):
res = []
for p in range(2, N):
if p * p > N:
break
if N % p != 0:
continue
e = 0
while N % p == 0:
e += 1
N //= p
res.append((p, e))
if N != 1:
res.append((N, 1))
return res
もし割り切れる素数があればそこでwhile文に突入し、Nがその数で割り切れなくなるまで続けます。
先のコードでは一回割ったら再度やり直していましたが、一回のfor文だけで行けるのがスマートできれいです。
最大公約数 -ユークリッド互除法-
最大公約数はユークリッド互除法を使って求めることができます。
実際のコードでは再帰関数を使います。
以下の通りです
def euclidean_algorithm(A:int, B:int) -> int:
larger = max(A,B)
smaller = min(A,B)
if smaller == 0:
return larger
else:
return euclidean_algorithm(smaller, larger%smaller)
再帰関数のポイントは、かならず終了条件を書かないといけないということです。もしこれを書かなかったら、while文のように無限ループになってしまいます。
以上、整数論に関する典型的なアルゴリズムのまとめでした。
参考