ゴールドバッハの予想について・・・

質問

ゴールドバッハの予想（4以上の任意の偶数は，2つの素数の和で表せる）を表すJavaプログラムを作りたいのですが、できるだけ計算経過時間を短縮したいんです。
　下のプログラムを改善して、計算経過時間が速くなるようにして下さい。
　どういう理由で改善したのかも付け加えてくれると嬉しいです。

--------------------------------------------------------------------------------------------------------------------------------
public class Gold {
static int prime(int number){
int count=0;
for(int i=1; i<=number; i++){
if(number%i==0) count++;
}
return count;
}

public static void main(String[] args) {

long start = System.currentTimeMillis();

int n, p;

for(n=4; n<100000; n+=2){

for(p=2; p<n; p++){
if(prime(p)==2 && prime(n-p)==2){
System.out.println(n + "=" + p + "+" + (n-p));
break;
}
}
if(p==n){
System.out.println("この予想は間違いと判明！");
break;
}

if(n%1000==0){
long stop = System.currentTimeMillis();
System.out.println(n + " " + (stop-start));
}
}
}
}
--------------------------------------------------------------------------------------------------------------------------------

回答No.1

tatsumi01 · ベストアンサー

Java は良くわからないので外しているかも知れませんが。
(1) 対象を 4 以上の偶数ではなく、6 以上の偶数にすると良いでしょう。4=2+2 は別に示す
すると素数は奇数だけですから、for(int i=1; i<=number; i++){ のところが二つ飛ばしにできます。
(2) for(int i=1; i<=number; i++){ のループ、number まで回しているのがムダ
素数判定は 2 以上、√number 以下の整数で割り切れば素数でないのでループの上限は√number で良い
number まで回す必要はなく、i で割り切れた時点で prime=1 として飛び出せばよい
ループを回り終わっても割り切れていなければ prime=2 で出る

素数判定はもっと高速な方法があると思いますが、とりあえずこれで。

お礼

わざわざアリガトウございます♪ほんとに助かります(^o^)
申し訳ないんですけど、もし良かったら、実際にJavaで書くとどうなるのかも示してくれませんか??

回答No.2

PecoPlus

こんばんは。

　きっと探せば、すごい最速のアルゴリズムとかあると思いますが、自分の頭で考えられる程度の最適化ですが・・・。

　素数は、自分と１以外では割り切れない数となっていますが、もっと、効率よく考えると、まず奇数であり、自分より小さいすべての素数で、割り切れない数といえます。

　素数の和であらわせるかというところで素数が必要で、ある数が素数であるかというところでまた素数が必要となります。

　そういったところから、何度も何度も同じ数を素数かどうか判別するよりも、いったん判別した素数をキャッシュしておいたほうがよいと考えました。

　それがこのクラスです。

-- PrimeCache.java --

import java.util.*;

public class PrimeCache implements Iterable<Integer> {
　　private ArrayList<Integer> list;

　　public PrimeCache() {
　　　　list = new ArrayList<Integer>();
　　　　list.add(3);
　　}

　　//素数かどうか判定するメソッド
　　public boolean isPrime(int n) {
　　　　if (n % 2 == 0) {
　　　　　　return false;
　　　　}

　　　　Iterator<Integer> iterator = iterator();
　　　　int prime;
　　　　while ((prime = iterator.next()) < n) {
　　　　　　if (n % prime == 0) {
　　　　　　　　return false;
　　　　　　}
　　　　}
　　　　return true;
　　}

　　//素数を昇順にアクセスできるイテレータを発行するメソッド
　　public Iterator<Integer> iterator() {
　　　　return new PrimeIterator();
　　}

　　private void addPrime() {
　　　　int lastPrime = list.get(list.size() - 1);
　　　　int i = lastPrime + 2;
　　　　while (true) {
　　　　　　if (pIsPrime(i)) {
　　　　　　　　list.add(i);
　　　　　　　　return;
　　　　　　}

　　　　　　i += 2;
　　　　}
　　}

　　private boolean pIsPrime(int n) {
　　　　if (n % 2 == 0) {
　　　　　　return false;
　　　　}

　　　　for (int p : list) {
　　　　　　if (n % p == 0) {
　　　　　　　　return false;
　　　　　　}
　　　　}

　　　　return true;
　　}

　　//イテレータ
　　//素数がキャッシュにあれば、それを返し、なければ、次の素数を探し、
　　//それを返すと同時にキャッシュに登録する。
　　private class PrimeIterator implements Iterator<Integer> {
　　　　private int index = 0;

　　　　public boolean hasNext() {
　　　　　　return true;
　　　　}

　　　　public Integer next() {
　　　　　　while (index > list.size() - 1) {
　　　　　　　　addPrime();
　　　　　　}

　　　　　　Integer prime = list.get(index);
　　　　　　index++;
　　　　　　return prime;
　　　　}

　　　　public void remove() {
　　　　　　throw new UnsupportedOperationException();
　　　　}
　　}
}

--------------------

　このPrimeCacheクラスを使った新しいGoldTestクラスがこれです。

-- GoldTest.java --

import java.util.*;

public class GoldTest {
　　private PrimeCache pCache;

　　public static void main(String[] args) {
　　　　GoldTest gold = new GoldTest();
　　　　long start = System.currentTimeMillis();
　　　　if (gold.verify(100000)) {
　　　　　　System.out.println("OK");
　　　　}
　　　　else {
　　　　　　System.out.println("この予想は間違いと判明！");
　　　　}
　　　　System.out.println(System.currentTimeMillis() - start);
　　}

　　public GoldTest() {
　　　　pCache = new PrimeCache();
　　}

　　public boolean verify(int max) {
　　　　for (int n = 4; n < max; n += 2) {
　　　　　　if (!isPrimeSum(n)) {
　　　　　　　　return false;
　　　　　　}
　　　　}
　　　　return true;
　　}

　　//素数の和で表せるか判定するメソッド
　　private boolean isPrimeSum(int n) {
　　　　Iterator<Integer> iterator = pCache.iterator();
　　　　int prime;
　　　　while ((prime = iterator.next()) < n) {
　　　　　　if (pCache.isPrime(n - prime)) {
　　　　　　　　//System.out.println(n + " = " + prime + " + " + (n - prime));
　　　　　　　　return true;
　　　　　　}
　　　　}
　　　　return false;
　　}
}
-------------------------

　100000を検証するのに１５秒くらいになりました。
　どうでしょう?