素数判定 / 約数列挙 / 素因数分解 / Smallest Prime Factor(osa_k法)
タイトル通り、素数判定、素因数分解、約数列挙のやり方について説明します。
素数の定義
ある正の整数$ Vが、$ 1と$ V以外のいずれの整数でも割り切れない時、$ Vは素数である。
素数判定
1. 愚直な判定法
「$ 1と$ V以外のいずれの整数でも割り切れない⇒素数である」の逆を考えると、
「$ 2以上$ V未満のいずれかの整数で割り切れる⇒素数ではない」になる。
(なお、$ Vより大きい整数で$ Vは割り切れない。)
これを愚直に書くと
code:cpp
bool isPrime(int v) {
if (v == 1) {
return false;
}
bool ans = true;
for (int i = 2; i < v; i++) {
if (v % i == 0) {
ans = false;
}
}
return ans;
}
code:py
def isPrime(v):
if v == 1:
return False
ans = True
for i in range(2, v):
if v % i == 0:
ans = False
return ans
以上の様になる。
(0 が入力され得る場合は条件分岐を修正してください。)
2. 高速化
先ほどの判定法は、時間計算量が$ Ο(N)であり、例えば$ 10^9を素因数分解するなどの場合は遅すぎて使えない。
ここで、例えば$ N = a \cdot bであるとしよう。
整数組$ (a, b)の積が$ Nであることが分かると、当然整数組$ (b, a)の積も$ Nであることが分かる。
ということは、$ a \leq bとしてしまっても、それを逆転させたものの組は発見されたも同然となる。
そこで、$ a \cdot b \leq Nと$ a \leq bをどちらも満たすような$ aの最大値について考える。
このとき、$ b = N \div aだから、
$ a = b = \sqrt Nの時が$ aの最大値となる(それ以上に$ aを大きくすると$ a \leq bではなくなる)。
よって、$ 2 \leq a \leq \sqrt Nとして$ Nを割り切る$ aがあるかを全て探索すればよい。
時間計算量は$ Ο(\sqrt N)まで改善される。
code:cpp
bool isPrime(int v) {
if (v == 1) {
return false;
}
bool ans = true;
for (int i = 2; i * i <= v; i++) {
if (v % i == 0) {
ans = false;
}
}
return ans;
}
code:py
def isPrime(v):
if v == 1:
return False
ans = True
for i in range(2, int(v**0.5)+1):
if v % i == 0:
ans = False
return ans
これならば、例えば$ N \leq 10^{12}でも素数判定ができる。
しかし、時に$ N \leq 10^6だが$ 10^5個の整数を素数判定しなくてはならない、といったケースがある。
約数列挙
約数列挙は、素数判定のプログラムを少し変更することで実現できる。
素数判定では約数の有無を$ 1つ見つければよかったのに対して、今回は全ての約数を見つけることになる。
(素数判定をbreakなどで高速化している場合には注意。)
ここでも先ほどの
$ a \leq bとしてしまっても、逆転させたものは発見されたも同然となる
ことを利用する。というのも、$ a \times b = Nならば、$ aのみならず$ bも$ Nの約数となるので、その両者を約数のリストに入れるだけになる。
code:cpp
void enumerateFactors(int v, vector<int>& fList){
fList.emplace_back(1);
fList.emplace_back(v);
for (int i = 2; i * i <= v; i++) {
if (v % i == 0){
fList.emplace_back(i);
fList.emplace_back(v / i);
}
}
}
code:py
def enumerateFactors(v):
for i in range(2, int(v**0.5)+1):
if v % i == 0:
ans.append(i)
ans.append(v / i)
なお、python では配列操作とfunctoolsを使うとワンライナーで書ける。
code:py
from functools import reduce
def enumerateFactors(v):
return reduce(lambda a, b : a + b, [i, n // i for i in range(2, int(v**0.5)+1) if n % i == 0], []) 素因数分解
これも先ほどまでの考え方を適用するだけである程度高速に出来る。
ただし今度は
$ 720720 = 2^4 \times 3^2 \times 5 \times 7 \times 11 \times 13
といったように分解する必要がある。
そこで、割れなくなるまで割るという操作を、素因数の小さい方から行う必要がある。
なお、先ほどから平然と小さい方から割っているが、これまでのは別に大きい方から割っても通るのに対し、今回は
$ pの倍数は$ pまたは$ pより大きい数以外にはない
というどう見ても当たり前な事実がネックとなって、大きい方から割ってはならないという制限が付く。
というのも、例えば$ 4で割れるイコール$ 2で$ 2回割れる、即ち$ 2^2で割れるということなので、
それを先に$ 4で割ってはいけない、というだけのことなのだが。
逆に、$ 2で割れるだけ割ると、割った後の数は素因数に$ 2を持たないので、後から$ 4だとか$ 12などの$ 2を素因数に持つ合成数では割れないようになる。
code:cpp
void primeFactorization(int v, vector<pair<int, int>>& pList) {
for (int i = 2; i * i <= v; i++) {
pair<int, int> pPair = {i, 0};
while (v % i == 0) {
pPair.second++;
v /= i;
}
if (pPair.second) {
pList.push_back(pPair);
}
}
if (v != 1){
pList.push_back({v, 1});
}
}
code:py
def primeFactorization(v):
ans = []
for i in range(2, int(v**0.5)+1):
while v % i == 0:
v //= i
ans.append(p)
if v != 1:
return ans
より高速な素因数分解 / Smallest Prime Factor / osa_k法
前述の通り、先ほどの方法だと、例えば$ N \leq 10^{12}で一度だけ素因数分解が必要という場合には、十分高速に素因数分解出来る。
しかし、時に$ N \leq 10^6だが$ 10^5個の整数を素因数分解しなくてはならない、といったケースがある。
このような場合に対応するための素因数分解法として、エラトステネスの篩を活用したものがある。
具体的には、
エラトステネスの篩では、素数でないと判断した数を消していた。ここで、素数でないと判断した数を消す代わりに、その数を割り切れる最小の素因数を記録する。
素因数分解をする時には、その表を元に$ Nの最小素因数で$ Nを割り、その答えが$ 1になるまで、割った結果で$ Nを置き換える。
以上の方法で、前半の篩作成は時間計算量$ Ο(N \log \log N)、後半の素因数分解は$ 1回ごとに時間計算量$ Ο(\log N)で処理できる。
code:cpp
using namespace std;
const int s = 1000000;
vector<int> sieve(s + 1, 0);
void primeFactorization(int v, vector<int>& pList) {
while(v > 1){
}
}
void initializeSieve(){
for(int i = 2; i * i <= s; i++){
for(int j = i * i; j <= s; j += i){
if(sievej == 0) sievej = i; }
}
}
for (int i = 2; i <= s; i++) {
if (sievei == 0) sievei = i; }
}
int main(){
initializeSieve();
int q; cin >> q;
while(q--){
int n; cin >> n;
vector<int> pList;
primeFactorization(n, pList);
for(int e : pList) cout << e << " ";
cout << endl;
}
}
code:py
s = 1000000
for i in range(2, int(s**0.5)+1):
for j in range(i*i, s + 1, i):
for i in range(2, s):
def primeFactorization(n):
if n == 1:
return []
return [sieven] + primeFactorization(n//sieven) q = int(input())
for _ in range(q):
n = int(input())
print(primeFactorization(n))
なお、エラトステネスの篩については時間計算量が$ Ο(N \log \log N)となることが分かっている。参考 また、ある整数$ Nについて、その素因数の個数は高々$ \log N個である。よって、素因数分解の時間計算量は$ Ο(\log N)となる。
素数判定への応用？
応用というか、こちらが元来のエラトステネスの篩なのだが。
先ほどの最小素因数を記録する部分を、たんに素数でないことを記録する、に変更するだけでよい。こちらは、素数判定$ 1回ごとの時間計算量が$ Ο(1)となる。
code:cpp
using namespace std;
const int s = 1000000;
vector<bool> sieve(s + 1, 1);
bool isPrime(int v){
}
void initializeSieve(){
for(int i = 2; i * i <= s; i++){
for(int j = i * i; j <= s; j += i){
}
}
}
}
int main(){
initializeSieve();
int q; cin >> q;
while(q--){
int n; cin >> n;
cout << isPrime(n) << endl;
}
}
code:py
s = 1000000
for i in range(2, int(s**0.5)+1):
for j in range(i*i, s, i):
def isPrime(n):
q = int(input())
for _ in range(q):
n = int(input())
print(isPrime(n))