【AtCoder】Pythonで素数判定・素数列挙・素因数分解
2021.06.25
2024.03.24
競技プログラミング
AtCoderPythonエラトステネスの篩素数
はじめに
AtCoderで出てくる素数に関する問題で使えそうなPythonのサンプルコードをまとめました。
素数に関するアルゴリズムを応用するような問題は、これらのコードを変更することで対応できると思います。
素数に関する問題
AtCoderなどで出てくる素数に関する問題は主に下記3つぐらいかと思います。
- 素数判定
- 素数列挙
- 素因数分解
これら3つのサンプルコードについて紹介します。
素数判定
まずはある数が素数かどうかを判定する問題になります。
判定する数が1つであればまでの整数で割り切れるかどうかで、ある程度の問題は判定できます。
サンプルコード
1import math
2
3def is_prime(n):
4 sqrt_n = math.ceil(math.sqrt(n))
5 for i in range(2, sqrt_n):
6 if n % i == 0:
7 return False
8 return True
以下のように使えます。
1n = int(input())
2print(is_prime(n))
153
2True
素数列挙
複数の数を素数かどうか判定して列挙するような問題はより高速は方法が必要になります。
素数の列挙にはエラトステネスの篩を利用します。
エラトステネスの篩は、N以下の素数を列挙するのに、2以上N以下の整数をまずは書き出します。その中から2から順に倍数を取り除いていくという処理を繰り返すことで素数のみにするアルゴリズムです。
N以下の素数の列挙
サンプルコード
1import math
2
3def sieve_of_eratosthenes(n):
4 prime = [True for i in range(n+1)]
5 prime[0] = False
6 prime[1] = False
7
8 sqrt_n = math.ceil(math.sqrt(n))
9 for i in range(2, sqrt_n):
10 if prime[i]:
11 for j in range(2*i, n+1, i):
12 prime[j] = False
13
14 return prime
以下のように利用することで素数の列挙、素数の数を求めることができます。
1n = int(input())
2
3# 素数の列挙
4prime = sieve_of_eratosthenes(n)
5for p in range(n+1):
6 if prime[p]:
7 print(p, end=' ')
8
9# 素数の数
10print(sum(prime))
111
22 3 5 7 11
35
特定の区間の素数
エラトステネスの篩を利用することで特定の区間の素数の列挙も可能です。
区間の素数を列挙する場合、以下の素因数として考えられるのはなので、の区間の素数での整数からその倍数を取り除いていくことで区間の素数を列挙することができます。
サンプルコード
1import math
2
3def segment_sieve(a, b):
4 sqrt_b = math.ceil(math.sqrt(b))
5 prime_small = [True for i in range(sqrt_b)]
6 prime = [True for i in range(b-a+1)]
7
8 for i in range(2, sqrt_b):
9 if prime_small[i]:
10 for j in range(2*i, sqrt_b, i):
11 prime_small[j] = False
12 for j in range((a+i-1)//i*i, b+1, i):
13 print('j: ', j)
14 prime[j-a] = False
15
16 return prime
以下のように利用することで素数の列挙と素数の数が求められます。
1a, b = map(int, input().split())
2
3seg_prime = segment_sieve(a, b)
4for p in range(b-a+1):
5 if seg_prime[p]:
6 print(p+a, end=' ')
7
8print(sum(seg_prime))
122 37
223 29 31 37
34
素因数分解
素因数分解は素数判定とほとんど同じで、2からまで順番に整数で割り切れるだけ割るという処理を繰り返します。
サンプルコード
1import math
2
3def factorization(n):
4 fact = []
5 for i in range(2, math.ceil(math.sqrt(n))):
6 if n % i == 0:
7 cnt = 0
8 while n % i == 0:
9 cnt += 1
10 n //= i
11 fact.append([i, cnt])
12
13 if n != 1:
14 fact[n] = 1
15
16 return fact
以下のように利用すると、[素因数, 指数]の形式で求めることができます。
1n = int(input())
2print(factorization(n))
124
2[[2, 3], [3, 1]]
参考
Share
関連記事
【AtCoder】bisectでリストを二分探索する
2021.09.10
【AtCoder】Pythonで優先度付きキュー
2021.08.03
【AtCoder】PythonでDPマスターその1〜初めの一歩〜
2021.07.10
【AtCoder】Pythonで二分探索
2021.10.01