素数・素因数分解

1. 整数$ Nまでの素数リストの作成　　　　　素数・素因数分解#63631ea08a5d6400005f97eb

2. 1つの整数$ Nの素数判定　　　　　　　　　　素数・素因数分解#6390b1c38a5d64000082d838

3. 1～$ Nのまでの$ N個の整数に対する素数判定　素数・素因数分解#6404295b8a5d64000046e9d2

4. 1つの整数$ Nの素因数分解　　　素数・素因数分解#6390b68a8a5d64000082d86e

5. 1～$ Nまでの$ N個の整数に対する素因数分解　　素数・素因数分解#640434b08a5d64000046ea12

6. 1から$ Nまでの素数の個数　　　素数・素因数分解#63638ede8a5d6400005f983a

1. 整数$ Nまでの素数リストの作成

(1) エラトステネスの篩【推奨】

有名な方法．$ O(N\log\log N)

説明ページ：アルゴ式 - エラトステネスの篩 (ふるい) を徹底解説〜実装から計算量まで〜

偶数だけ先にFalseにして，奇数の奇数倍だけ篩に掛けるバージョンもある．

code: python

# ### 素数リストの作成（エラトステネスの篩） ###

def make_primes(n: int) -> list:

is_prime = True * (n + 1) # is_primen：nが素数なら1，そうでないなら0．初期値は1

is_prime0 = is_prime1 = False

m = 2

while m * m <= n: # 除数は nの平方根まで．Pythonはforの方が速いので，forにしてもよい．

if is_primem:

for km in range(m * m, n + 1, m):

is_primekm = False

m += 1

return [m for m in range(n + 1) if is_primem] # nまでの素数（リスト）

# 使用例

print(make_primes(100)) # 100までの素数リスト．2, 3, ..., 97

(2) 線形篩

エラトステネスとは異なる方法による篩．

1から$ Nまでの各整数$ iの最小素因数$ lpf(i)を求めるときに使われるのが特徴（エラトステネスの篩でも導出可能）

計算量は$ O(N)であるが，実計算時間ではエラトステネスの篩の方が速い場合も多く，優位性は低そう．

参考：https://kanpurin.hatenablog.com/entry/2021/08/14/115825#senkeifurui

整数$ iを最小素因数$ lpf(i)で割った値$ d=i/lpf(i)を考える．$ dを順に大きくして，$ lpf(i)を確定させる．

数値例：

$ d=2のとき，$ d=2が素数リストに追加．$ lpf(4=2\times2)=2が確定

$ d=3のとき，$ d=3が素数リストに追加．$ lpf(6=2\times3)=2,\ lpf(9=3\times3)=3が確定

$ d=4のとき，$ lpf(4)=2．$ lpf(8=2\times4)=2が確定

$ d=5のとき，$ d=5が素数リストに追加．$ lpf(10=2\times5)=2,\ lpf(15=3\times5)=3,\ lpf(25=5\times5)=5が確定

$ d=6のとき，$ lpf(6)=2．$ lpf(12=2\times6)=2が確定．$ p > lpf(6)=2である$ pに対して$ lpf(18=3\times6)=3,\ lpf(30=5\times6)=5とはしない．

$ d=7のとき，$ d=7が素数リストに追加．$ lpf(14=2\times7)=2,\ lpf(21=3\times7)=3,\ lpf(35=5\times7)=5,\ lpf(49=7\times7)=7が確定

$ d=8のとき，$ lpf(8)=2．$ lpf(16=2\times8)=2が確定．$ p > lpf(8)=2である$ pに対して$ lpf(24=3\times8)=3,\ lpf(40=5\times8)=5,\ lpf(56=7\times8)=7とはしない

$ d=9のとき，$ lpf(9)=3．$ lpf(18=2\times9)=2,\ lpf(27=3\times9)=3が確定．$ p > lpf(9)=3である$ pに対して$ lpf(45=5\times9)=5,\ lpf(63=7\times9)=7とはしない

$ d=10のとき，$ lpf(10)=2．$ lpf(20=2\times10)=2が確定．$ p > lpf(10)=2である$ pに対して$ lpf(30=3\times10)=3,\ lpf(50=5\times10)=5,\ lpf(70=7\times10)=7とはしない

code: python

def linear_sieve(n: int) -> list:

prime_list = [] # 発見した素数のリスト

lpf = None * (n + 1) # lpfi：整数 iの最小素因数

for d in range(2, n + 1): # d = i // lpfi．d >= lpfi

if lpfd is None: # dが素数の場合

lpfd = d

prime_list.append(d)

for p in prime_list:

if p * d > n or p > lpfd:

break

lpfp * d = p # p <= lpfdのおかげで，lpfp * dは1回しか代入されない

return prime_list

# 使用例

print(linear_sieve(100)) # 100までの素数リスト．2, 3, ..., 97

2. 1つの整数$ Nの素数判定

(1) 整数$ Nまでの素数リストを作成する方法

上記１の方法で$ Nまでの素数リストを作成して，集合に変換して，集合内に存在するか確認する．

計算量：リスト作成＋$ O(1)

code:python

# 使用例（作成済みの素数リストを用いる場合）

primes = make_primes(1000) # 1000までの素数リスト．2, 3, ..., 997

print(997 in set(primes)) # 997が素数か？　True

(2) $ \sqrt{N}までの数で割れるかチェックする方法【推奨】

計算量$ O(\sqrt N)

code:python

def judge_prime(n: int) -> bool:

if n % 2 == 0:

return False

m = 3

while m * m <= n: # n の平方根までチェック

if n % m == 0:

return False

m += 2 # 奇数のみチェック

return True

print(judge_prime(997)) # 997が素数か？ True

3. 1～$ Nまでの$ N個の整数に対する素数判定

(1) 整数$ Nまでの素数リストを作成する方法【推奨】

上記1の方法で$ Nまでの素数リストを作成して，集合に変換して，各整数が集合内に存在するか確認する．

計算量：リスト作成＋$ O(N)

code:python

# 使用例

primes = make_primes(1000) # 1000までの素数リスト．2, 3, ..., 997

for i in range(1, 1000+1):

print(i in set(primes)) # iが素数ならTrue，素数でないならFalse

(2) 1～$ Nまでの整数に対して個別に素数か判定する方法

2(2)の方法で，各整数が素数か判定する方法．

計算量$ O(N\sqrt N)．実装は容易だが，計算速度は3(1)の方法より劣る．

code:python

# 使用例

primes = make_primes(1000) # 1000までの素数リスト．2, 3, ..., 997

for i in range(1, 1000+1):

print(judge_prime(i)) # iが素数ならTrue，素数でないならFalse

4. 1つの整数$ Nの素因数分解

2～$ \sqrt{N}までの整数で割れるだけ割り続ける．

$ \sqrt{N}まで割っても値が残っているときには，その数も掛けることを忘れない．

計算量 $ O(\sqrt N)

参考サイト：アルゴ式 - 素因数分解のアルゴリズム

code: python

# ### 素数因数分解

def factorization(n: int) -> dict:

from collections import defaultdict

factors = defaultdict(int)

for i in range(2, n):

if i * i > n:

break # i <= √N まで

while n % i == 0:

factorsi += 1

n //= i

if n > 1:

factorsn = 1

return factors

# 使用例

print(factorization(120)) # 120を素因数分解した辞書． {2:3, 3:1, 5:1} --> 2^3 * 3^1 * 5^1

5. 1～$ Nまでの$ N個の整数に対する素因数分解

(1) 個別に素因数分解する方法

上記4の方法を整数1～$ Nのそれぞれに対して行う．実装が簡単．

計算量$ O(N\sqrt N)

(2) エラトステネスの篩，最小素因数$ lpfを使う方法【推奨】

エラトステネスの篩を拡張して，$ \sqrt{N}までの素数リストと，最小素因数$ lpfのリストを作成する．

$ nを$ lpf(n)で割れるだけ割り続ける．

計算量 $ O(N\log N)

参考サイト：エラトステネスの篩の活用法を総特集！〜高速素因数分解・メビウスの反転公式〜

code: python

def main():

# ### Nまでの素数リスト + 最小素因数リストの作成 ###

def make_primes_lpf(n: int) -> tuple:

is_prime = True * (n + 1) # is_primen：nが素数なら1，そうでないなら0．初期値は1

is_prime0 = is_prime1 = False

lpf = list(range(n + 1))

lpf0 = lpf1 = -1 # 存在せず

m = 2

while m * m <= n: # 除数は nの平方根まで．Pythonはforの方が速いので，forにしてもよい．

if is_primem:

for km in range(m * m, n + 1, m):

is_primekm = False

if lpfkm == km:

lpfkm = m

m += 1

prime_list = [m for m in range(n + 1) if is_primem]

return prime_list, lpf

# ### 1～Nまでの素数因数分解リスト．O(NlogN)

def factorization_list(n: int) -> list:

from collections import defaultdict

# 1～nまでの素数リストと最小素因数リストを作成

primes, lpf = make_primes_lpf(n)

# 1～nまでの素因数分解を保存するリスト

factors = defaultdict(int) for _ in range(n + 1)

for i in range(2, n + 1):

ii = i

while ii > 1:

p = lpfii # 割る数

exp = 0 # 割った回数

# iiをlpfiiで割れるだけ割る

while lpfii == p:

ii //= p

exp += 1

factorsip = exp # pでexp回割った

return factors

# 使用例

primes, lpf = make_primes_lpf(100)

print(primes) # 100までの素数リスト．2, 3, ..., 97

print(lpf) # 100までの最小素因数リスト．-1, -1, 2, 3, 2, 5, 2, 7, ...

n = 100

factors = factorization_list(n) # nまでの素因数分解リスト

for i in range(2, n + 1):

print(i, factorsi) # 2 {2: 1}, 3 {3: 1}, 4 {2: 2}, 5 {5: 1},...

main()

6. 1から$ Nまでの素数の個数

素数定理より，近似的に$ N/\log(N)個

表になっていて便利なサイト　　　https://www.benricho.org/primenumber/kazu.html

TODO: ポラードロー法を調べる

https://ja.m.wikipedia.org/wiki/ポラード%E3%83%BBロー素因数分解法

#数学 #素数 #素因数分解 #約数 #倍数