アルゴリズム

で割っていく の各数で割り切れるだけ割っていくことで素因数分解することができる。この時の計算量は。そのためが大きい場合は実行時間が大きくなる。 の中には素数でない数(合成数)も存在する可能性があるが、その合成数を構成する素数は...

与えられたNが素数かどうか判定するアルゴリズム でひたすら割る のいずれで割ってもNが割り切れないことを確認する。計算量は def is_prime_number(n: int): for i in rang...