ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »素数
このページの記事一覧

【Java】素因数分解をする  


 素数関連のアルゴリズムとして、簡単な「素因数分解」もやってみよう。といってもこれまでとほとんど変わらないので、解説は必要なら「試し割り」や「エラトステネスの篩」の記事を見て欲しい。コードも少し手を加えただけの代物なので、必要あれば色々改造して使うと良いだろう。

●素因数分解のリストを作る
import java.util.ArrayList;
import java.util.List;

/**<h1>素因数分解のリストを作る</h1>
* @param n : 素因数分解する値 (>=0)
* @return<b>List<Integer></b> : 素因数分解のリスト
*/
public static final List<Integer> primeFactor(int n) {
final List<Integer> list = new ArrayList<Integer>();
if (n < 2) { //n が2以上とわかっていれば、ここは不要
return list;
}

while (n != 1 && n % 2 == 0) { //2で割り切れるだけ割る
list.add(2);
n >>>= 1; //÷2 の代わり
}

for (int i = 3; i * i <= n; i += 2) { //奇数のみ [O(√n[/2])で可]
while (n % i == 0) {
list.add(i);
n /= i;
}
}

if (n != 1) {
list.add(n);
}
return list;
}


//メインでは...
int n = 240;
List<Integer> factor = primeFactor(n);
for (int v : factor) {
System.out.print(v + " ");
}

2 2 2 2 3 5

 今回も素数系のアルゴリズムの関連になるため、ポイントは変わらない(というより本当に同じようなコードばかりで書けることがわかる(笑))。念のため n が0と1のときにも対応させてあるが、素数とは「1とそれ自身でしか割り切れない、2以上の整数」と定義されているので、不要なら0と1ははじめから除外しても良い(2以上を使うこと前提ならば、関数内冒頭の「if (n < 2)~」は削除しても構わない)。

 上記の例では個々の素因数を要素にしているが、それぞれの値とその個数のように連想配列にするのも良い。以下の例では戻値の型を変更しただけで、内容は同じものだ。用途によって使い分けるのが良いだろう。

●素因数分解の連想配列を作る
import java.util.HashMap;
import java.util.Map;

/**<h1>素因数分解の連想配列を作る</h1>
* @param n : 素因数分解する値 (>=0)
* @return<b>Map<Integer, Integer></b> : <値, 個数> の連想配列
*/
public static final Map<Integer, Integer> primeFactorMap(int n) {
final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
if (n < 2) { //n が2以上とわかっていれば、ここは不要
return map;
}

while (n != 1 && n % 2 == 0) { //2で割り切れるだけ割る
if (map.containsKey(2)) {
map.put(2, map.get(2) + 1);
} else {
map.put(2, 1);
}
n >>>= 1; //÷2 の代わり
}

for (int i = 3; i * i <= n; i += 2) { //奇数のみ [O(√n[/2])で可]
while (n % i == 0) {
if (map.containsKey(i)) {
map.put(i, map.get(i) + 1);
} else {
map.put(i, 1);
}
n /= i;
}
}

if (n != 1) {
map.put(n, 1);
}
return map;
}


//メインでは...
int n = 240;
List<Integer> factor = primeFactorMap(n);
for (Map.Entry<Integer, Integer> e : factor.entrySet()) {
System.out.print(e.getKey() + " = " + e.getValue() + ", ");
}

2 = 4, 3 = 1, 5 = 1,

 戻値は「素因数の値=その個数」となる。つまり、上の例の場合「素因数の 2 が 4 個、3 が 1 個、 5 が 1 個(2×2×2×2×3×5 = 240)」という意味になる。

 素因数分解にも「ポラード・ロー素因数分解法」や「数体ふるい法」などのより高度なアルゴリズムもある。ググッてみれば pdf の資料などがいくつか見つかるので、興味があれば調べてみるのも良いだろう。だがまぁ、オンラインジャッジの出題などではこの程度のアルゴリズムでも十分いける。

(参考)
素因数分解アルゴリズム
数体篩法


(関連記事)
【Java】素数判定①(試し割り法)
【Java】素数判定②(エラトステネスの篩(ふるい))
【Java】素数判定③(サンダラムの篩(ふるい))
【Java】素数判定④(アトキンの篩(ふるい))


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  素数 
tb: 0   cm: --

【Java】素数判定③(アトキンの篩(ふるい))  


 「より現代的なアルゴリズム」(Wikipedia)と書いてあるので、たぶんそうなのだろう(笑)。残念ながら英語版しかないのだが、「エラトステネスの篩」のような篩系のアルゴリズムで、「アトキンの篩」というものもある。内容的には更なる奇数の分類わけという感じだが、説明は大変そうなので、こちらのサイトへ丸投げしよう(笑)。私も「ふむふむナルホド」と頷きつつ、たぶん本当の意味は理解していない(笑)。「奇数を分類し、いくつかの方程式の解が奇数個なら素数」という話が書いてあるね。とりあえず色々試してみたら確かに正しい答えが出たので、私としては問題ない(笑)。

(参考)
アトキンのふるい

 内容的にはいくつかのソースを試して、一番高速だったものを、具体的な値を返すように改造しただけのものだ。コードもほぼそのまま。

●素数のリストを作る②(アトキンの篩(ふるい))
import java.util.ArrayList;
import java.util.List;

/**<h1>素数のリストを作る(アトキンの篩)</h1>
* <p>奇数を分類わけし、いくつかの方程式の解での判別と平方数を取り除く篩をかける。</p>
* @param n : 取得する素数の最大の値 (>=0) [n を含む]
* @return<b>List<Integer></b> : 素数のリスト
*/
public static final List<Integer> primeListAtkin(final int n) {
final List<Integer> list = new ArrayList<Integer>();
if (n < 2) { //n が2以上とわかっていれば、ここは不要
return list;
}
list.add(2);
if (n == 2) { //n が3以上とわかっていれば、ここは不要
return list;
}

final boolean[] sieve = new boolean[n + 1];
final int sqr = (int)Math.sqrt(n);

int k;
for (int i = 1; i <= 5; i += 4) {
for (int y = i; y <= sqr; y += 6) {
for (int x = 1; x <= sqr && (k = 4 * x * x + y * y) <= n; x++) {
sieve[k] = !sieve[k];
}
for (int x = y + 1; x <= sqr && (k = 3 * x * x - y * y) <= n; x += 2) {
sieve[k] = !sieve[k];
}
}
}
for (int i = 2; i <= 4; i += 2) {
for (int y = i; y <= sqr; y += 6) {
for (int x = 1; x <= sqr && (k = 3 * x * x + y * y) <= n; x += 2) {
sieve[k] = !sieve[k];
}
for (int x = y + 1; x <= sqr && (k = 3 * x * x - y * y) <= n; x += 2) {
sieve[k] = !sieve[k];
}
}
}
for (int i = 1; i <= 2; ++i) {
for (int y = 3; y <= sqr; y += 6) {
for (int x = i; x <= sqr && (k = 4 * x * x + y * y) <= n; x += 3) {
sieve[k] = !sieve[k];
}
}
}
for (int i = 5; i <= sqr; i += 2) {
if (sieve[i]) {
for (int j = i * i; j <= n; j += i * i) {
sieve[j] = false;
}
}
}
sieve[2] = sieve[3] = true;

for (int i = 3; i <= n; i += 2) {
if (sieve[i]) {
list.add(i);
}
}
return list;
}


//メインでは...
int n = 100;
List<Integer> primes = primeListAtkin(n);
for (int v : primes) {
System.out.print(v + " ");
}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

 今回も他のアルゴリズムと比較のため、n が0と1のときにも対応させてある。素数とは「1とそれ自身でしか割り切れない、2以上の整数」と定義されているので、不要なら0と1ははじめから除外しても良い(2以上または3以上を使うこと前提ならば、関数内冒頭の「if (n < 2)~」「if (n == 2)~」は削除しても構わない)。なるべく同じ条件で比較したかったので、「エラトステネスの篩」や「サンダラムの篩」のコードに合わせたら、関数冒頭が少し長くなってしまった。

 実際にこれまでに作った「エラトステネスの篩」と「サンダラムの篩」とこの「アトキンの篩」を比較してみると、「アトキンの篩」「サンダラムの篩」「エラトステネスの篩」の順に速い。ただし、篩(ふるい)の真偽値(sieve[])でだけなら、「アトキンの篩」「エラトステネスの篩」「サンダラムの篩」となった。実装の仕方もあるのだろうが、やはりコンピュータ時代に生み出された「アトキンの篩」のアルゴリズムの方が比較的速いようだ。とは言え「エラトステネスの篩」は改造しやすいため、出題に合わせて最適化しやすいメリットもある。逆に数式が複雑に絡むコードは改造がしづらく、手を加えればバグを埋め込むことにもなり兼ねないので、スピード特化で使うのも良い気がする。結局は複数のアルゴリズムを知っている方がメリットを活かせるのかも知れない。

 ググっていて感じたのは「サンダラムの篩」はあまり例がないのに対し、「アトキンの篩」は思いのほか実装例がたくさんあったことだ。なので色々試したが、やはりなるべく平方根や除算を使わず、シンプルな実装の方が速かった。isPrime() のとき書いたポイントは非常に小さなことだけど、実は意外と効果は高い。以下にその実装例を挙げておくが、アルゴリズムはすべて同じなわけだから、その「ちょっとした違い」で実行速度が変わることを感じてみるのも勉強になるかも知れない。

(参考)
アトキンのふるい
エラトステネスの篩 vs アトキンの篩
アトキンの篩
ダメ出し:アトキンの篩
Rubyで、「エラトステネスのふるい」を改良したと言われる「アトキンのふるい」をいまさら実装する
Atkinの篩


(関連記事)
【Java】素数判定②(エラトステネスの篩(ふるい))
【Java】素数判定③(サンダラムの篩(ふるい))
【Java】素数判定①(試し割り法)


category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  素数  数列 
tb: 0   cm: --

【Java】素数判定③(サンダラムの篩(ふるい))  


 「エラトステネスの篩」とは別の方法で篩(ふるい)をかけていく方法で、「サンダラムの篩」というものもある。内容的には数学の証明のような感じで、素数と合成数の種類から分類するような感じになる。Wikipedia の説明ではわかりづらいので、こちらのサイトなどを見ると良いだろう。具体的でわかりやすく、C言語のソースも載っている。内容的にはこのソースをほぼそのままで、具体的な値を返すように改造しただけのものである。

●素数のリストを作る②(サンダラムの篩(ふるい))
import java.util.ArrayList;
import java.util.List;

/**<h1>素数のリストを作る(サンダラムの篩)</h1>
* <p>整数 n > 1 は、素数または合成数で、合成数だけを篩い落せば素数が残される。</p>
* @param n : 取得する素数の最大の値 (>=0) [n を含む]
* @return<b>List<Integer></b> : 素数のリスト
*/
public static final List<Integer> primeListSundaram(final int n) {
final List<Integer> list = new ArrayList<Integer>();
if (n < 2) { //n が2以上とわかっていれば、ここは不要
return list;
}

final int h = ((n + 1) >>> 1); //÷2 の代わり
final boolean[] sieve = new boolean[h];

int k;
for (int i = 1; i * i <= n; i++) {
for (int j = i; (k = i + j + 2 * i * j) < h; j++) {
sieve[k] = true; //k = 4,7,10,12,13,16,17,…
}
}

list.add(2);
for (int i = 1; i < h; i++) {
if (!sieve[i]) {
list.add(2 * i + 1); //素数の数列
}
}
return list;
}


//メインでは...
int n = 100;
List<Integer> primes = primeListSundaram(n);
for (int v : primes) {
System.out.print(v + " ");
}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

 今回も他のアルゴリズムと比較も兼ねて、n が0と1のときにも対応させてある。素数とは「1とそれ自身でしか割り切れない、2以上の整数」と定義されているので、不要なら0と1ははじめから除外しても良い(2以上を使うこと前提ならば、関数内冒頭の「if (n < 2)~」は削除しても構わない)。

 サンダラムの篩ではエラトステネスの篩のときのように、篩だけ(boolean[] 配列だけ)の例は掲載しなかったが、この篩は「偶数の合成数と奇数の合成数を篩った数列」であって、素数のフラグそのものではないためだ。エラトステネスの篩と同じようにフラグの配列が欲しければ、関数内でもう1つ配列を作り、最後のリストを作っている部分(list.add(2 * i + 1))を配列に変えれば良い。ただし、2つ配列を作りオーダーがO(n/2)のためか、篩だけならエラトステネスの篩の方が速い(エラトステネスは配列1つでO(√n))。またリストを作る場合はO(n/2)で良いためか、サンダラムの篩の方が速い(エラトステネスはO(n))。実装にもよると思うが、使い分けしても良いかも知れない。

 コードは比較のため、前回に合わせた書き方という感じもあるが、他に参考になったサイトなども載せておこう。配列やリスト、言語の特質なんかもあるかも知れないが、色々試してみると「なるほどな~」と思ったりする(笑)。

(参考)
サンダラムの篩 (MEMORANDUM)
サンダラムの篩 (Trivial Contents)
サンダラムの篩 (私的数学塾)

 もう1つ、現代風のアルゴリズム(?)の「アトキンの篩」というものもある。Wikipedia では英語版しかないが、他のサイトで用例があったので次回やってみよう。


(関連記事)
【Java】素数判定②(エラトステネスの篩(ふるい))
【Java】素数判定④(アトキンの篩(ふるい))
【Java】素数判定①(試し割り法)


category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  素数  数列 
tb: 0   cm: --

【Java】素数判定②(エラトステネスの篩(ふるい))  


 前回の isPrime() は1つの数値が素数かどうかを調べる方法だったが、今回の「エラトステネスの篩(ふるい)」は素数かどうかの一覧のような感じのもの。Wikipedia にも書いてあるように、コンピュータがある以前からあるアルゴリズムである。「ユークリッドの互除法」に並んで最古のアルゴリズムとも言われているらしい。故にわかりやすく、色々応用しやすい長所がある。その内容はググればいくらでも出てくるので他のサイトに譲るが、Wikipedia の右端にあるアニメーションを見ているだけでもその方法は十分にわかると思う。

 今回は素数かどうかのフラグを列挙した配列と実際の素数の値を列挙したリストを作ってみよう。

●素数かどうかを判定する②(エラトステネスの篩(ふるい))
/**<h1>エラトステネスの篩(素数フラグ)を作る</h1>
* <p>偶数以外で、3 から √n までに対して順番に倍数をふるい落としていく。</p>
* @param n : 調べる素数の最大の値 (>=0) [n を含む]
* @return<b>boolean[]</b> : 素数である数のインデクスが true となる配列
*/
public static final boolean[] eratosthenesSieve(final int n) {
final boolean[] sieve = new boolean[n + 1]; //素数フラグ
if (n < 2) { //n が2以上とわかっていれば、ここは不要
return sieve;
}

sieve[2] = true;

for (int i = 3; i <= n; i += 2) { //2の倍数以外(奇数)を候補にする
sieve[i] = true;
}

for (int i = 3; i * i <= n; i += 2) { //奇数のみ [O(√n[/2])で可]
if (sieve[i]) {
for (int j = i * 2; j <= n; j += i) { //倍数を候補から除外する
sieve[j] = false;
}
}
}
return sieve;
}


//メインでは...
int n = 10;
boolean[] sieve = eratosthenesSieve(n);
for (int i = 0; i < sieve.length; i++) {
System.out.print(sieve[i] + " "); //素数である i が true になる
}

false false true true false true false true false false false

 真偽値は素数となるインデクスの数が true となる(上の例の場合、[2], [3], [5], [7] が true となっているので、2~10(n) までの数の中で 2, 3, 5, 7 が素数ということを表している)。

 素数とは「1とそれ自身でしか割り切れない、2以上の整数」と定義されているので、0と1ははじめから除外しても良いが、前回の isPrime() が0と1にも対応していたので、比較のため合わせておいた。2以上を使うこと前提ならば、関数内冒頭の「if (n < 2)~」は削除しても構わない。

 コード自体は isPrime() とあまり変わらないので、必要なら前回の解説を見て欲しい。

 もう1つ、今度は具体的な素数の値のリストを返す関数を作ろう。作り方は簡単で、上記のエラトステネスの篩をしながら、true となっている値をリストに追加してくだけだ。

●素数のリストを作る①(エラトステネスの篩(ふるい))
import java.util.ArrayList;
import java.util.List;

/**<h1>素数のリストを作る(エラトステネスの篩)</h1>
* <p>偶数以外で、3 から √n までに対して順番に倍数をふるい落としていく。</p>
* @param n : 取得する素数の最大の値 (>=0) [n を含む]
* @return<b>List<Integer></b> : 素数のリスト
*/
public static final List<Integer> primeListEratosthenes(final int n) {
final List<Integer> list = new ArrayList<Integer>();
if (n < 2) { //n が2以上とわかっていれば、ここは不要
return list;
}

final boolean[] sieve = new boolean[n + 1]; //素数フラグ
sieve[2] = true;
list.add(2);

for (int i = 3; i <= n; i += 2) { //2の倍数以外(奇数)を候補にする
sieve[i] = true;
}

//エラトステネスのふるい
for (int i = 3; i <= n; i += 2) { //奇数のみ[リスト作成のため O(n[/2])]
if (sieve[i]) {
list.add(i);
for (int j = i * 2; j <= n; j += i) { //倍数を候補から除外する
sieve[j] = false;
}
}
}

return list;
}


//メインでは...
int n = 100;
List<Integer> primes = primeListEratosthenes(n);
for (int v : primes) {
System.out.print(v + " ");
}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

 今回は簡単にするため、List を用いているが、配列を戻値にしても良いだろう。ただ、配列の場合はあらかじめ要素数を決めないといけないので、篩(sieve[i])が true になっているものをカウントしておいて(上記の例の場合、リストに追加(list.add())している場所)、カウント後に配列のインスタンスを生成する必要がある。または取り得る最大の個数(上限値)が決まっているなら、引数に配列の参照を受け取り、値を順に追加した上で、最後に追加したインデクスを戻値として返す方法もある(メインではその戻値で [0]~[idx] の間だけ使うようにする)。具体的な値のリストが必要ないなら、篩の真偽値だけの方がもちろん速い。

 ちなみに「n までの素数の個数」は「素数定理」や「ベルトランの仮説」にある通り、「n が十分大きいときには n と 2n の間の素数の個数は n / log n に近いことが言え、特にベルトランの仮説によって保証されている1つの素数の存在よりもより強く、より多くの素数が n と 2n の間に存在していることが分かる」(Wikipedia)と言われているので、「n / log n」で近似してみるのも良いかも知れない。または「ルジャンドルの素数定理」で「n 以下の素数の個数は n/(log n - 1.08366) で近似できる」とか「リーマンゼータ関数」など色々あるようなので、覗いてみると面白いかも知れない。ただ、私もいくつか試してみたが、元々「与えられた数より小さい素数の個数」なので、配列の要素数定義には使えなかった(n + 1 したり、関数の答えを +1 してみたが、素数の個数が必要な配列の要素数を上回る個数になることもある[ArrayIndexOutOfBoundsException])。いい加減な個数で良いのなら「n * 1.25505871293248 / log n」あたりにしておくと、n までの素数の個数が上回ることはないようだ(この係数は全探索で算出したものなので、Java 以外で適用できるかわからないが…(→実数計算は言語によって微妙に誤差が出るため))。まぁ、無駄は多くなるが n 個で要素数を作っても良いと思う。参考までに素数の個数に関する資料を載せておこう。

(参考)
素数定理の歴史
素数個数関数の近似、素数定理、グラフ
平方数間の素数の個数(1)平方数間の素数の個数(2)

 ネットに落ちているサンプルコードも同じアルゴリズムでありながら、実装によって実行速度は随分違うので、配列やリスト、真偽値のみなど、用途に合わせて使い分けた方が良いだろう。特にエラトステネスの篩は他のアルゴリズムと違って改造しやすい利点があるので、例えば「開始~終了インデクスの間だけ値を取り出す」とか、n を上限数ではなく「n 個の素数を取り出す」など簡単に作れる。オンラインジャッジでの出題でも利用頻度は高いので、いくつかのパターンをライブラリとして作っておくとかなり役に立つだろう。

 他にも同じ篩系のアルゴリズムとして「サンダラムの篩」というものもある。せっかくなので、比較のためにも少しだけやってみよう。


(関連記事)
【Java】素数判定③(サンダラムの篩(ふるい))
【Java】素数判定④(アトキンの篩(ふるい))
【Java】素数判定①(試し割り法)


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  素数  数列 
tb: 0   cm: --

【Java】素数判定①(試し割り法)  


 数学的な問題を解いていると非常によくテーマとして挙げられる素数。数学者体質の人はよくハマってしまうほど興味深い性質もあるらしいのだが、コードとしても似たようなものが使えるので、ちょこっと取り上げてみることにした。その定義は「正の約数が 1 と自分自身のみであるもののことで、ただし 1 は(現在では)含めない。正の約数の個数が 2 である自然数と言い換えることもできる。(~以下略~)」(Wikipedia)となっているが、簡単に言えば「何らかの数の倍数でない」とか「素数の反対は合成数である」とだけ覚えていれば十分かも知れない。あと「2の倍数(偶数)は2以外は素数でないことから、素数のほとんどは奇数である」と覚えておくとコードを書くとき、その計算量を半分にできることが多い。

●素数かどうかを判定する(試し割り法)
/**<h1>素数かどうかを判定する(試し割り法)</h1>
* <p>偶数以外で、3 から √n までに対して順番に割り切れるものが存在しないことをチェックする。</p>
* @param n : 調べる値 (n >= 0) [n を含む]
* @return<b>boolean</b> : true = 素数 (1 は例外で false)
*/
public static final boolean isPrime(final long n) {
if (n < 2) {
return false;
}
if (n % 2 == 0) {
return (n == 2);
}

for (long i = 3; i * i <= n; i += 2) { //奇数のみ [O(√n[/2])で可]
if (n % i == 0) {
return false;
}
}
return true;
}


//メインでは...
long n = 46116646144580591L;
System.out.println(isPrime(n));

true

 引数の型が long になっているが、int の範囲で十分なら型を変えても良いだろう。実際に int 範囲の場合、以下に示す高速化のポイントは、あまり効果は見えない(非常に大きな値のときよくわかる)。

 今回のコードはお手本そのままという感じなので、目新しいものはないが、このコードを取り上げたのは「ちょっとした高速化のポイント」がいくつか含まれているからだ。そのポイントは今後取り上げようと思っている「素数表(エラトステネスの篩)」や「素因数分解」「約数」など数学的なコードに頻繁に出てくる。実際には非常に細かいテクニックなのだが、使うと使わないでは効率が結構変わるものなので、改めて考えてみよう。

 まず一番目立つのはループ部分の「i * i <= n」となっている所だろうか。これは言ってみれば「i <= √n」と同じ意味だ。だから、以下のように書くこともできる

●ループ部分の「i * i <= n」の別表記1
~(略)~
for (long i = 3; i <= Math.sqrt(n); i += 2) {
//処理
}
~(略)~

●ループ部分の「i * i <= n」の別表記2
~(略)~
for (long i = 3; i <= n / i; i += 2) {
//処理
}
~(略)~

 実際に色々なサンプルコードを見てみると、このような表記も非常に多いのだが、見つけたら試しに「i * i <= n」のような掛け算の表記にしてみよう。特に非常に大きな計算やサーバーサイドのスクリプト、ゲームなどのメインスレッドループなどでは実行速度が大きく改善されることがある。というのは平方根(sqrt)や sin, cos, log などの算術関数、除算(割り算)などはコンピュータにとっては思いのほか負荷が高く、大量に計算すると重くなるからだ(ただの1回のようなものならそれほど問題ない)。もしどうしても使いたいときは、ループ外で1回計算し、変数にその答えを入れて利用するとか、「n / 2」を「n >> 1(ビットシフト)」(平方数で割るとき)などにするという手もある。まぁ、実際のところやり過ぎるとコードがわかりづらくなるのでほどほどにしておいた方が良いかもしれないが(笑)、ピンポイントで高速化できる箇所を修正するだけでもかなり効果はある。

 あとは冒頭に書いたように素数判定に偶数を一気に除外している所だろうか。コードの「if (n % 2 == 0)」とループの「i += 2」となっている箇所だ。こうすると一気に候補を半分にできるわけで、意外と見落としがちだったりする。できるだけループ回数を減らすのは実行速度の向上に繋がる。ループの √n 化も同じことで、「n が約数 d を持ったとすると、n/d も n の約数で、n = n * n/d なので、min(d, n/d) <= √n となる(d または n/d の小さい方の数は必ず √n 以下となる)」。O(√n )というのは非常に高速なので、使える箇所には積極的に使おう(数学的な関数では意外と使えることが多い)。

 他にも素数判定法には「AKS素数判定法」とか「フェルマーテスト」(確率的=正しいとは限らない答えが出ることがある)「ミラー–ラビン素数判定法」(確率的)などもあるようだが、CodeIQなどに出題されるプログラミング問題では「エラトステネスの篩(ふるい)」のような篩法で十分だろう。実際に私は中級(★★)~上級(★★★★)問題をすべて解いているが、素数関連の問題でエラトステネスの篩を使ってタイムアウトしたことは一度もない(←せっかくなので作った関数などを実際の問題によく試させて貰っている(笑))。興味があるなら、より高度な素数判定法の参考も以下に載せておこう。

(参考)
素数判定法
AKS素数判定法のアルゴリズム


(関連記事)
【Java】素数判定②(エラトステネスの篩(ふるい))
【Java】素数判定③(サンダラムの篩(ふるい))
【Java】素数判定④(アトキンの篩(ふるい))


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  素数 
tb: 0   cm: --
IS<インフィニット・ストラトス> アーキタイプ・ブレイカー
キルドヤ


プロフィール

Twitter

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop