素数判定
- 割り切れるかどうかの判定は√Nまでしか見なくていい。
-
N = a * b (a <= b)とした時に、aで割り切れることが判定できていればbで割れるかを判定する必要がない。 - すなわち、最大でも
a = bのケースまで割れるかを判定してあげればいいことになるので、N = a * b = a * a = a ** 2を満たすaまで見ればいい。 - O(√N)
# 素数判定
def isPrime(n: int):
# validation chech
if n < 0:
raise("[ERROR] parameter must be not less than 0 (n >= 0)")
if n == 0 or n == 1:
return False
for i in range(2, n + 1):
# √N以下まで見ればいい。i*iとして比較するのは小数を扱いたくないため。
if i * i > n:
return True
if n % i == 0:
return False
# 素数判定
N = 7
print(isPrime(N))
# True
素数列挙 / エラトステネスの篩
- Nまでのリストを用意して、素数に該当するものが見つかったらその倍数を削除していく。
- 上と同じく√NまででOK
- 倍数削除は
i ** 2から行うのは、それまでの処理でi * (i - 1)はふるい落とされているため。
eg.) i = 5のとき、 5 * 2、5 * 3、5 * 4はいずれも、2の倍数、3の倍数、2の倍数として落とされている。
# エラトステネスの篩
# 素数列挙 (区間指定可)
def getPrimes(last: int, first: int = 1):
# validation check
if not isinstance(last, int) or \
not isinstance(first, int):
raise("[ERROR] parameter must be integer")
if last < 0 or first < 0:
raise("[ERROR] parameter must be not less than 0 (first >= 0 & last >= 0)")
if last < first:
last, first = first, last
isPrime = [True] * (last + 1) # 素数かどうか
# 0と1をFalseに
isPrime[0] = isPrime[1] = False
for i in range(2, int(last ** 0.5 + 1)):
if isPrime[i]:
# 篩にかける。iの倍数をすべてFalseにしていく。このとき i^2まではすでにふるい落とされているので見る必要がない
for j in range(i ** 2, last + 1, i):
isPrime[j] = False
return [i for i in range(first, last + 1) if isPrime[i]]
# 素数列挙
N = 10 # 末尾の数字を含む
print(getPrimes(N))
# [2, 3, 5, 7]
# 素数列挙
F = 13
L = 23 # 末尾の数字を含む
print(getPrimes(F, L))
# [13, 17, 19, 23]
# 素数の個数
N = 10 ** 7
print(len(getPrimes(N)))
# 664579
# 2.5sくらい
約数列挙
約数を高速で列挙するコード(Python)参考にしました。
ソートされて出てくる。
# 約数列挙
def getDivisors(n: int):
# validation check
if not isinstance(n, int):
raise("[ERROR] parameter must be integer")
if n < 0:
raise("[ERROR] parameter must be not less than 0 (n >= 0)")
lowerDivisors, upperDivisors = [], []
i = 1
while i * i <= n:
if n % i == 0:
lowerDivisors.append(i)
if i != n // i:
upperDivisors.append(n//i)
i += 1
return lowerDivisors + upperDivisors[::-1]
# 約数列挙
N = 120
print(getDivisors(N))
# [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]
複数の整数に対して約数の個数取得(別の手法)
- 上のコードで約数を取得してリストの長さから算出するというのを、1からNまで繰り返してもいいが、別の手法。
- 約数側をループさせていき、その約数を持つものはカウントさせていく。
- この時にその約数自体をリストに含めてしまえば、複数の整数に対して一発で約数のリストも求められそう。
- O(NlogN)。10^7とかだと列挙は厳しい。
# 約数の個数を一斉取得
def getNumsOfDivisorsOfEachNumbers(n: int):
# validation check
if not isinstance(n, int):
raise("[ERROR] parameter must be integer")
if n < 0:
raise("[ERROR] parameter must be not less than 0 (n >= 0)")
nums = [0] * (n + 1) # 0-indexed
for i in range(1, n + 1):
for j in range(i, n + 1, i):
nums[j] += 1
nums.pop(0)
return nums
# 約数の個数を一斉取得
N = 10
print(getNumsOfDivisorsOfEachNumbers(N))
参考) AtCoderのABC172 D問題
素因数分解
- 冷静に割ってもいってもいいが、上と同じように複数の数に対して素因数を同時に求めたい時に有用な方法。
- エラトステネスの篩において倍数を削除していく時にフラグで管理するのではなく、なんの数で割ったのかを記載しておくことde後から辿ることができるようにしている。
- ダブリングに似た方法で素因数を取得していく。
eg.) 例えば10を素因数分解するとき。
- リストの10を参照する。
- 10を2で割れるので2を素因数リストに加え、
- 10/2=5から保養の5に対応するところを見る。
- 5は5と書かれており素数とわかるので判定を終了する。
import time
# 素因数分解
def primeFactrization(n: int):
# validation check
if not isinstance(n, int):
raise("[ERROR] parameter must be integer")
if n < 0:
raise("[ERROR] parameter must be not less than 0 (n >= 0)")
dividableMinimunPrime = [i for i in range(0, n + 1)] # 数iを割りきる最小の素数
for i in range(2, int(n ** 0.5 + 1)):
if dividableMinimunPrime[i] == i:
for j in range(i ** 2, n + 1, i):
if dividableMinimunPrime[j] == j: # 条件を削除して上書きを許可すると得られる素因数が降順になる。
dividableMinimunPrime[j] = i
# ダブリングと同じ要領で進めていく
primeFactors = []
rest = n
while dividableMinimunPrime[rest] != rest:
primeFactors.append(dividableMinimunPrime[rest])
rest //= dividableMinimunPrime[rest]
primeFactors.append(rest)
return primeFactors
N = 200000
start = time.time()
print(primeFactrization(N))
elapsedTime = time.time() - start
print("time: {} [sec]".format(elapsedTime))
# [2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5]
# time: 0.05865812301635742 [sec]
# time: 0.07313990592956543 [sec]
# time: 0.05380010604858399 [sec]
参考) AtCoder ABC152 E問題