「内容別リスト/数学系/素因数分解」の編集履歴（バックアップ）一覧はこちら

「内容別リスト/数学系/素因数分解」(2025/05/17 (土) 02:35:15) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

#contents
----

*雑な説明
与えられた数を素数の積に分解するアルゴリズム。
毎回O(n)かかるものと、前処理にO(n*loglogn)かかるがその後は毎回O(logn)ですむものがある。

*レベル
ABCのC問題以降。

*アルゴリズム内容1
[[素数判定]]と同じ要領で2から小さい順に割っていく。
割りきれる場合、それが何回割れるか確認し、出力に詰める。
その際、一度調べた素数については二度と調べないので、本当に割ってしまうとよい。
平方が残っている数より大きくなれば残ったものは素数である。
O(√n)で済むが、計算結果の使いまわしが効かないので、大量に素因数分解するには不向き。

C++での実際の参考コードは以下。
 vector<pair<int,int>> prime_factorization(int n) {
   vector<pair<int,int>> primes;
   int p = 2;
   while (p*p<=n) {
     int counter = 0;
     while (n%p==0) {
       counter++;
       n /= p;
     }
     if (counter>0) primes.emplace_back(p,counter);
     p++;
   }
   if (n>1) primes.emplace_back(n,1);
   return primes;
 }

*アルゴリズム内容2（D問題レベル）
[[エラトステネスの篩]]のところで解説してあるn未満の全ての数の最小素因数を求めるアルゴリズムを利用する。
その結果を利用すれば次に割れる素数は何か、それで何回割れるかもすぐわかる。
毎回の処理がO(logn)で済むが、最初にO(n*loglogn)かかる準備が必要になる。
10^9クラスのnが混ざっていると苦しい。

C++での実際の参考コードは以下。
上半分は最小素因数を求めるやつ。
 vector<int> smallest_primes (int n) {
   vector<int> primes(n,-1);
   bool flag = true;
   for (int i=2; i<n; i++) {
     if (primes.at(i)!=-1) continue;
     primes.at(i) = i;
     if (!flag) continue;
     for (long long j=i*i; j<n; j+=i) {
       if (primes.at(j)==-1) primes.at(j) = i;
     }
     if (1LL*i*i>=n) flag = false;
   }
   return primes;
 }
 
 vector<pair<int,int>> prime_factorization(int n, const vector<int>& smallest_primes) {
   vector<pair<int,int>> primes;
   while (n>1) {
     int p = smallest_primes.at(n);
     int counter = 0;
     while (smallest_primes.at(n)==p) {
       counter++;
       n /= p;
     }
     primes.emplace_back(p,counter);
   }
   return primes;
 }
 
   // main関数内
   auto vec = smallest_primes(n+1);
   auto vec2 = prime_factorization(n,vec);
main関数内で、[[素因数分解]]する可能性がある最大の数より1大きい数を渡さないといけないことに注意。
 
*注意点

*関連アルゴリズム
-[[素数判定]]
素数かどうか判定するだけで、分解はしないやつ。

-[[エラトステネスの篩]]
n未満の全ての素数を洗い出すアルゴリズム。
判定したい個数が多いなら、あちらを使った方が全体としては速い場合もある。

-[[約数の個数と総和]]
正の整数nに対して、その（正の）約数がいくつあるか、正の約数の総和がいくつになるかを求める。
素因数分解を利用して効率的に求めることができる。

#contents
----

*雑な説明
与えられた数を素数の積に分解するアルゴリズム。
毎回O(n)かかるものと、前処理にO(n*loglogn)かかるがその後は毎回O(logn)ですむものがある。

*レベル
ABCのC問題以降。

*アルゴリズム内容1
[[素数判定]]と同じ要領で2から小さい順に割っていく。
割りきれる場合、それが何回割れるか確認し、出力に詰める。
その際、一度調べた素数については二度と調べないので、本当に割ってしまうとよい。
平方が残っている数より大きくなれば残ったものは素数である。
O(√n)で済むが、計算結果の使いまわしが効かないので、大量に素因数分解するには不向き。

C++での実際の参考コードは以下。
 vector<pair<int,int>> prime_factorization(int n) {
   vector<pair<int,int>> primes;
   int p = 2;
   while (p*p<=n) {
     int counter = 0;
     while (n%p==0) {
       counter++;
       n /= p;
     }
     if (counter>0) primes.emplace_back(p,counter);
     p++;
   }
   if (n>1) primes.emplace_back(n,1);
   return primes;
 }

*アルゴリズム内容2（D問題レベル）
[[エラトステネスの篩]]のところで解説してあるn未満の全ての数の最小素因数を求めるアルゴリズムを利用する。
その結果を利用すれば次に割れる素数は何か、それで何回割れるかもすぐわかる。
毎回の処理がO(logn)で済むが、最初にO(n*loglogn)かかる準備が必要になる。
10^9クラスのnが混ざっていると苦しい。

C++での実際の参考コードは以下。
上半分は最小素因数を求めるやつ。
 vector<int> smallest_primes (int n) {
   vector<int> primes(n,-1);
   bool flag = true;
   for (int i=2; i<n; i++) {
     if (primes.at(i)!=-1) continue;
     primes.at(i) = i;
     if (!flag) continue;
     for (long long j=i*i; j<n; j+=i) {
       if (primes.at(j)==-1) primes.at(j) = i;
     }
     if (1LL*i*i>=n) flag = false;
   }
   return primes;
 }
 
 vector<pair<int,int>> prime_factorization(int n, const vector<int>& smallest_primes) {
   vector<pair<int,int>> primes;
   while (n>1) {
     int p = smallest_primes.at(n);
     int counter = 0;
     while (smallest_primes.at(n)==p) {
       counter++;
       n /= p;
     }
     primes.emplace_back(p,counter);
   }
   return primes;
 }
 
   // main関数内
   auto vec = smallest_primes(n+1);
   auto vec2 = prime_factorization(n,vec);
main関数内で、[[素因数分解]]する可能性がある最大の数より1大きい数を渡さないといけないことに注意。
 
*注意点

*関連アルゴリズム
**[[素数判定]]
素数かどうか判定するだけで、分解はしないやつ。

**[[エラトステネスの篩]]
n未満の全ての素数を洗い出すアルゴリズム。
判定したい個数が多いなら、あちらを使った方が全体としては速い場合もある。

**[[約数の個数と総和]]
正の整数nに対して、その（正の）約数がいくつあるか、正の約数の総和がいくつになるかを求める。
素因数分解を利用して効率的に求めることができる。