初心者のための素数配列を構築するより効率的な方法

Question

おはようございます。私はちょうどJAVAの最初のコースを完了し、夏の新鮮なものを保つためにオンラインプロジェクトを探していました。私はプロジェクトのオイラーのウェブサイトを見つけて、問題10を完成させようとしています。私は素数の配列を作るためにこのアルゴリズムを書いていました。しかし、numberOfPrimes = 100000以上で実行しようとすると数分かかります。

私はそれを理解するスキルがないかもしれませんが、私はより効率的な方法があると仮定しています。いずれにせよアドバイスをいただければ幸いです。

 int[] arrayOfPrimes = new int[numberOfPrimes]; 
     arrayOfPrimes[0] = 2; 


     for(int i = 1; i < numberOfPrimes; i++) 
     { 
      int n = arrayOfPrimes[(i - 1)] + 1; 


      for(int j = 0; j < i; j++) 
      { 
       if(n % arrayOfPrimes[j] == 0) 
       { 
        n++; 
        j = -1; //resets to 0 at the next iteration. 
       } 
      } 

      arrayOfPrimes[i] = n; 
     } 

Answer 1

その最高のあなたが簡単に操作し、あなたはここにしたいと、このコードを試してみてくださいできるだけ多くの数字を取ることができますのArrayListを使用することです： -

int numberOfPrimes=100000; 

ArrayList<Integer>Primes = new ArrayList<>(); 

Primes.add(2); 

int i=3; 
Primes.add(i); 
for(int j = 0; j < Primes.size(); j++){//Checks all previous prime numbers before the new number 
if(i%Primes.get(j)==0){//Checks if prime number at j is divisible by i 

if(Primes.size()>numberOfPrimes){//breaking out of loop after reaching above numberOfPrimes 

Primes.remove(Primes.size()-1);//Removes the last non prime number 
    break; 
} 
Primes.remove(Primes.size()-1);//Removes the non prime number 
j=-1;//resets j to start from 0 
i++;//next number 
Primes.add(i);//adding it for next check 
} 
if(j==Primes.size()-2){//Another resting condition when all previous prime numbers are checked 
j=-1; 
i++; 
Primes.add(i); 
} 
} 
//end 

for(int j = 0; j < Primes.size(); j++){// just for printing 
System.out.println(Primes.get(j)); 
} 

が、それは約1を取りましたmin 7秒で100000を達成します。もう1つはループを使用して配列を印刷します。

クラス

Answer 2

あなたはあなたがnをdevideしようとしているプラ​​イムはnの平方根よりも大きいかどうかを確認することができます。それは10万まであなたを得るはずです。

しかし、素数の任意の大きな連続配列を得る方法はありません。

ここで変更されたコード

int numberOfPrimes = 100000; 
int[] prime = new int[numberOfPrimes]; 
prime[0] = 2; 

for (int i = 1; i < numberOfPrimes; i++) { 
    int n = prime[(i - 1)] + 1; 

    int sqrtN = (int)(Math.sqrt(n)) + 1; 

    for (int j = 0; j < i && prime[j] < sqrtN; j++) { 
     if (n % prime[j] == 0) { 
      n++; 
      j = -1; // resets to 0 at the next iteration. 
     } 
    } 

    prime[i] = n; 
}