Support
\ この記事が役に立ったと思ったら、サポートお願いします！ /
Share
関連記事
【AtCoder】Pythonでキューを使う
2021.08.15
【AtCoder】Pythonで優先度付きキュー
2021.08.03
Pythonでビット単位演算とシフト演算
2021.06.13
【AtCoder】Pythonで二分探索
2021.10.01
\ この記事が役に立ったと思ったら、サポートお願いします！ /
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から順に倍数を取り除いていくという処理を繰り返すことで素数のみにするアルゴリズムです。
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]]