ヽ|∵|ゝ(Fantom) の 開発blog? ホーム » Java »【Java】素数判定③(サンダラムの篩(ふるい))

【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: --


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/211-7e5c55dc
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop