7

Project Eulerの問題7をやっています。私がすべきことは、10,001 番目の素数を計算することです。(素数とは、それ自体と 1 だけで割り切れる 1 より大きい整数です。)

これが私の現在のプログラムです：

public class Problem7 {
    public static void main(String args[]) {
        long numberOfPrimes = 0;
        long number = 2;

        while (numberOfPrimes < 10001) {
            if (isPrime(number)) {
                numberOfPrimes++;
            }
            number++;
        }
        System.out.println("10001st prime: " + number);
    }

    public static boolean isPrime(long N) {
        if (N <= 1)
            return false;
        else
            return Prime(N, N - 1);
    }

    public static boolean Prime(long X, long Y) {
        if (Y == 1)
            return true;
        else if (X % Y == 0)
            return false;
        else
            return Prime(X, Y - 1);
    }
}

100番目の素数などの検索では問題なく動作しますが、非常に大きな入力 (10,001 など) で実行すると、スタック オーバーフローが発生します。なぜ、どうすればこれを修正できますか?

4

13 に答える 13

30

Prime問題は、数が素数であるかどうかを判断するために再帰的に呼び出していることだと思います。したがって、1000という数が素数であるかどうかを判断するには、Prime1000回再帰的に呼び出します。各再帰呼び出しでは、データをスタックに保持する必要があります。スタックは非常に大きいだけなので、最終的にはスタックのスペースが不足して、再帰的な呼び出しを続けます。再帰的なソリューションの代わりに反復的なソリューションを使用してみてください。

于 2010-03-21T02:30:03.880 に答える
8

「エラトステネスのふるい」を使う

Java ソース:

public class Main {
    public static void main(String args []){
        long numberOfPrimes = 0;
        int number = 1;
        int maxLimit = 10000000;
        boolean[] sieve = new boolean[maxLimit];
        for ( int i = 2; i < maxLimit; i++ ) {
            if ( sieve[i] == true ) continue;

            numberOfPrimes++;

            if ( numberOfPrimes == 10001 ) {
                number = i;
                break;
            }

            for ( int j = i+i; j < maxLimit; j += i )
                sieve[j] = true;
        }
        System.out.println("10001st prime: "+ number);
    }
}
于 2010-03-22T14:42:54.507 に答える
4

これまでに取得したすべての素数をルックアップリストに保存する必要があるため、その数がそのリストの数で除算されているかどうかを確認します。そうでない場合は素数です-リストに追加してください。
もう1つのアイデアは、を除いた偶数が素数でなくなったらすぐに置き換えnumber++;てnumber += 2;チェックを開始することです。32

于 2010-03-21T02:30:36.260 に答える
2

私は最近この問題を解決しました。エラトステネスのふるいで素数を生成することをお勧めします。たとえば、すべての素数が100万未満であると言います。実装するのは難しいアルゴリズムではなく、必要な素数の数に対してかなり高速です。

于 2010-03-21T02:34:13.657 に答える
2

一部の言語（Lispのような多くの関数型および半関数型言語など）のコンパイラーは、使用したような末尾再帰を反復に変換しますが、（明らかに）Javaコンパイラーはそれを行いません。その結果、すべての再帰呼び出しはスタックスペースを使用し、最終的には不足してスタックがオーバーフローします。

もちろん、ほとんどの目的で、別のアルゴリズムを使用する必要があります。現在使用しているものは、これらの処理が進むにつれてかなりひどいものになります。少なくとも、テストする数値の平方根までの奇数をチェックするだけで済みます...

于 2010-03-21T02:35:14.820 に答える
1

素数をテストする戦略は、小さい自然数ごとに割り切れるかどうかを確認することです。

小さい素数ごとに割り切れるかどうかをテストするように戦略を変更すると、大量の計算を節約できます。

于 2010-03-21T06:38:21.593 に答える
1 
import java.util.*;

public class LargestPrime {
    public static boolean isPrime(long s) {
        for(long i = 2; i < s; i++) {
            if((s % i) == 0) return false;                   
        }
        return true;
    }

    public static void main(String[] args) {
        LargestPrime p = new LargestPrime();
        LinkedList<Long> arr = new LinkedList<Long>();
        for(long j = 2; j <= 999999; j++) {

            if(isPrime(j)) arr.add(j);

        }
        // System.out.println("List of Prime Number are: "+ arr);
        long t = arr.get(10001);

        System.out.println("The Prime Number At 10001st position: " + t);
    }
}
于 2011-06-29T03:53:25.503 に答える
0

これを一般的に解決するには、再帰的なソリューションから反復的なソリューションに切り替える必要があります。（すべての再帰的アルゴリズムは反復的に表現することもできます。）

関数Primeは再帰的であるため、それ自体を呼び出すことができる回数には常にシステム制限があります。

ただし、システムに10001に達するのに十分なメモリがある場合があります。Javaでは、VMが使用するメモリの最大量（スタック、ヒープなど）を設定できます。スタックメモリ数を増やすと、おそらくそれを作成できるようになります。このページを見る

http://docs.sun.com/source/817-2180-10/pt_chap5.html

一部のJavaVMオプション。

于 2010-03-21T02:30:13.803 に答える
0 
package problems;

public class P_7 {
    /**
     * @param args
     */
    public static boolean prime(double num)
    {
        double x=2;
        double limit=(int) ((num/2)-(num/2)%1);
        while(x<=limit)
        {
            if(num%x==0)
                return false;
            x++;
        }
        return true;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int i=1;
        int j=3;
        while(i<=10000)
        {
            if(prime(j))
            {
                System.out.println(i);
                i++;
                System.out.println(j);
            }
            j++;
        }
    }
}

これは私の実用的な答えです。

于 2012-05-16T10:15:12.677 に答える
0

Rabin-Miller primality testはいつでも使用できます。アルゴリズムの実装は非常に簡単で非常に高速ですが、その仕組みを理解するのは少し難しいです。

于 2010-03-22T14:50:17.130 に答える
0

問題は再帰的に定義されたPrime(X,Y)関数にありますが、使用されるアルゴリズムにもあります。Java の関数呼び出しメカニズムが対応できる再帰の深さは非常に限られているため、呼び出しスタックが使い果たされ、「スタック オーバーフロー」エラーが発生します。

テスト対象の数の平方根を下回るすべての数に対して割り切れるかどうかをテストするだけで十分です。OP コードに関しては、 からPrime(N,N-1)ではなく、から開始することを意味しPrime( N, floor( sqrt( N+1)) )ます。再帰の深さが 10000 からわずか 100 に変更されるため、この変更だけで、この特定のタスクの SO エラーを防ぐのに十分な場合があります。

アルゴリズムの問​​題はそこから始まります。Prime(X,Y)コードはカウントダウンするため、最初に大きな数値で数値をテストします。しかし、より小さな要因がはるかに頻繁に見つかります。カウントは、可能な限り最小の係数 2 (数字の 50% で発生) から候補番号のまで行う必要があります。この機会に、関数も単純なループsqrtとして書き直してください。while

次の簡単で明白な改善は、偶数を完全に無視することです。2 は素数であることが知られています。他のすべてのイベントはそうではありません。つまり、 からループを開始し、numberOfPrimes = 1; number = 3;でカウントアップしnumber += 2て奇数のみを列挙し、 で始まり、テストしてでカウントアップするループで、奇数isPrime(N)のみで割り切れるかどうかもテストすることを意味します。whileX = 3N % XX += 2

または疑似コード(実際には Haskell) では、元のコードは

main = print ([n | n<-[2..], isPrime(n)] !! 10000)  where   
  isPrime(n) = _Prime(n-1)  where
      _Prime(y) = y==1 || (rem n y > 0 && _Prime(y-1)) 
  -- 100:0.50s 200:2.57s 300:6.80s 10000:(projected:8.5h)
  --       n^2.4       n^2.4

提案された修正:

main = print ((2:[n | n<-[3,5..], isOddPrime(n)]) !! 10000)  where   
  isOddPrime(n) = _Prime(3)  where
         _Prime(y) = (y*y) > n || (rem n y > 0 && _Prime(y+2)) 
  -- 100:0.02s 200:0.03s 300:0.04s 5000:3.02s 10000:8.60s
  --                                       n^1.5

示されているタイミングは、GHCi でコンパイルされていないコード (低速のラップトップ) の場合です。として取られた経験的な局所的な成長次数log(t2/t1) / log(n2/n1)。奇数ではなく素数でテストすると、さらに高速になります。

ところで、元のコードは 10001 番目の素数ではなく、その上の数字を出力します。

于 2012-05-17T09:55:40.927 に答える
0

Cでは...短いバージョンを実行できますが、何でも:D ..

#include <stdio.h>
#include <stdlib.h>

prost_br(int p)
{
    int br=0;

    for(int i=2;i*i<=p;i++)
    if(p%i==0)
    br++;

    if(br==0)
    return 1;
    return 0;
}

int main()
{
    long i=1;
    int br=0;
FILE *a;

a=fopen("10001_prst_numbers.txt","w");
if(a==NULL){printf("\nError!\a\n"); exit(1);}

    while(br!=10001)
    {
        i++;
        if(prost_br(i))
        {
            br++;
            fprintf(a,"%d ",i);
        }

    }
    char s[]={"10001th prime number is: "};
fprintf(a,"\n%s %d",s,i);
fprintf(stdout,"\n10001th prime number is: %d\n\a",i);

fclose(a);
system("Pause");
}
于 2013-01-21T03:04:33.867 に答える
0

公開クラスのプログラム {

public int nthPrime(int nth) {
    int ctr = 0;
    int num = 0;
    int x = 2;
    int infinite = 15;          // initial value good for 6 prime values
    while(x < infinite) {
        boolean isPrime = true; 
        for(int i = 2; i <= x / 2; i++) {
            if(x % i == 0) {
                isPrime = false;
            }
        }
        if(isPrime) {
            System.out.println(x);  // optional
            ctr++;
            if(ctr == nth) {
                num = x;
                break;
            }
        }
        x++;
        if(x == infinite) {     // for bigger nth requested prime value
            infinite++;     
        }
    }
    return num;
}

public static void main(String[] args) {
    int ans = new progs().nthPrime(10001);
    System.out.println("nth prime number is " + ans);
}

}

于 2013-09-04T02:31:03.633 に答える