「素因数分解」がなんぼのもんじゃい！
どうもボクです。
「素因数分解」を高速化する必要が出て参りまして、ちょいと調べてみました。
ちなみに、量子コンピューターとか使えれば、当然、高速化されると。
⇧ 上記サイト様が詳しいです。だが、しかし！時代は、まだ量子コンピューターを気軽に使える状態ではないと。
というわけで、アルゴリズム探検隊！
素因数分解 とは？
高速化を考える前に、そも、「素因数分解」とは何ぞや？
素因数分解 (そいんすうぶんかい、英: prime factorization) とは、ある正の整数を素数の積の形で表すことである。ただし、1に対する素因数分解は 1 と定義する。
素因数分解には次のような性質がある。
⇧ とあり、
インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は、巨大な合成数の素因数分解を実用的な時間内に実行することが困難であることと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解のアルゴリズムが活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。
⇧ 結構、Webとかのセキュリティに関わってるらしい...
素因数分解とは、
のような 素数 × 素数 × ... っていう風な形に表すことであると。
素因数分解のアルゴリズム
Wikipediaさんによりますと、
正の整数 N を素因数分解するための最も単純な方法は、2 から順に √N までの素数で割っていく方法（試し割り法）である。しかし、N が大きくなると、この方法では困難である。
大きな N に対しては以下のような方法がある。
- ρ法（ポラード・ロー素因数分解法）
- p − 1 法
- p + 1 法
- 連分数法
- 楕円曲線法 (ECM, Elliptic curve method)
- 複数多項式2次ふるい法 (MPQS, Multiple polynomial quadratic sieve)
- 数体ふるい法 (NFS, Number field sieve)
- 一般数体ふるい法 (GNFS, General number field sieve)
- 特殊数体ふるい法 (SNFS, Special number field sieve)
とあるんだと。
んで、Aizu Online Judge の問題で、
時間切れみたいになってしまったんで、アルゴリズムを考えないとアカンのだと。
tutuz.hateblo.jp
sucrose.hatenablog.com
んで、「エラトステネスの篩」ってアルゴリズムがイケてるらしい。
⇧ Java 8 の StreamAPI で実装できるようです。
時代は「エラトステネスの篩」と思ったら、
⇧ 「アトキンの篩」ってのも存在するんだと...もう、どうしたら良いんだろう...。
ただ、今回は、
⇧ 上記サイト様の方法でイケました。偶数の素数は「2」しか存在しないため、あとは奇数の素数を考えれば良いんだという衝撃。
package main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class PrimeFactory {
public static void main(String[] args) {
// TODO 自動生成されたメソッド・スタブ
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
try {
String strNum = br.readLine();
sb.append(strNum + ":");
int number = Integer.parseInt(strNum);
int devideNum = 2;
while (number % devideNum == 0) {
sb.append(" ");
sb.append(devideNum);
number /= 2;
}
devideNum++;
while (number != 1) {
if (number % devideNum == 0) {
sb.append(" ");
sb.append(devideNum);
number /= devideNum;
} else {
devideNum +=2;
}
}
// for (int i= devideNum; i <= number; i++) {
// if (number < devideNum) {
// break;
// }
// devideNum = i;
// while ((number % devideNum) == 0) {
// number /= devideNum;
// sb.append(" ");
// sb.append(devideNum);
// }
// }
} catch (IOException e) {
// TODO 自動生成された catch ブロック
e.printStackTrace();
}
System.out.println(sb.toString());
}
}
んで、イケました。
アルゴリズムとか勉強せねばですかね...
今回はこのへんで。
