[競プロ用]素数とか約数とか素因数分解まとめ - Qiita

素数判定 割り切れるかどうかの判定は√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