【AtCoder】Pythonで素数判定・素数列挙・素因数分解

2021.06.25
2024.03.24
競技プログラミング
AtCoderPythonエラトステネスの篩素数

本ページはAmazonアフィリエイトのリンクを含みます。

はじめに

AtCoderで出てくる素数に関する問題で使えそうなPythonのサンプルコードをまとめました。

素数に関するアルゴリズムを応用するような問題は、これらのコードを変更することで対応できると思います。

素数に関する問題

AtCoderなどで出てくる素数に関する問題は主に下記3つぐらいかと思います。

  • 素数判定
  • 素数列挙
  • 素因数分解

これら3つのサンプルコードについて紹介します。

素数判定

まずはある数が素数かどうかを判定する問題になります。

判定する数が1つであればn\sqrt{n}までの整数で割り切れるかどうかで、ある程度の問題は判定できます。

サンプルコード

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

特定の区間の素数

エラトステネスの篩を利用することで特定の区間の素数の列挙も可能です。

区間[a,b][a, b]の素数を列挙する場合、bb以下の素因数として考えられるのはb\sqrt{b}なので、[2,b][2, \sqrt{b}]の区間の素数で[a,b][a ,b]の整数からその倍数を取り除いていくことで区間[a,b][a, b]の素数を列挙することができます。

サンプルコード

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からn\sqrt{n}まで順番に整数で割り切れるだけ割るという処理を繰り返します。

サンプルコード

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]]

参考

Support

\ この記事が役に立ったと思ったら、サポートお願いします! /

buy me a coffee
Share

Profile

author

Masa

都内のIT企業で働くエンジニア
自分が学んだことをブログでわかりやすく発信していきながらスキルアップを目指していきます!

buy me a coffee