与えられた範囲内のすべての素数を見つける

Question

私はこのJavaプログラムを書いており、与えられた範囲内のすべての素数を見つけます。私が本当に大きな数字を扱っているので、コードが十分に速くないようで、時間エラーが出ます。ここに私のコードはありますが、誰もがそれをより速くすることを知っていますか？ありがとう。

import java.util.*; 
public class primes2 
{ 
    private static Scanner streamReader = new Scanner(System.in); 
    public static void main(String[] args) 
    { 
     int xrange = streamReader.nextInt(); 
     int zrange = streamReader.nextInt(); 
     for (int checks = xrange; checks <= zrange; checks++) 
     { 
      boolean[] checkForPrime = Primes(1000000); 
      if (checkForPrime[checks]) 
      { 
       System.out.println(checks); 
      } 
     } 
    } 
    public static boolean[] Primes(int n) 
    { 
     boolean[] isPrime = new boolean[n + 1]; 
     if (n >= 2) 
      isPrime[2] = true; 
     for (int i = 3; i <= n; i += 2) 
      isPrime[i] = true; 
     for (int i = 3, end = sqrt(n); i <= end; i += 2) 
     { 
      if (isPrime[i]) 
      { 
       for (int j = i * 3; j <= n; j += i << 1) 
        isPrime[j] = false; 
      } 
     } 
     return isPrime; 
    } 
    public static int sqrt(int x) 
    { 
     int y = 0; 
     for (int i = 15; i >= 0; i--) 
     { 
      y |= 1 << i; 
      if (y > 46340 || y * y > x) 
       y ^= 1 << i; 
     } 
     return y; 
     } 
} 

Answer 1

あなたは、この変更によって巨大改善を得ることができます：あなたの現在のコードは、ふるいzrange - xrange + 1回を再生成しますが、実際にあなた

boolean[] checkForPrime = Primes(1000000); 
    for (int checks = xrange; checks <= zrange; checks++) 
    { 

：これまで

for (int checks = xrange; checks <= zrange; checks++) 
    { 
     boolean[] checkForPrime = Primes(1000000); 

を一度しか生成する必要はありません。

Answer 2

明らかな問題は、多くの時間（zrange - xrange times）まで1000000までの素数を計算しているということです。もう1つは1000000までの素数を計算する必要はないので、zrangeまで素数をチェックする必要があるのでzrange < 1000000のときに時間を無駄にし、zrange> 1000000のときにバッファオーバーフローが発生する。

Answer 3

の代わりにfor (int j = i * i; j <= n; j += i << 1)と書くと、内部ループをi*iから開始することができます。

また、zrangeが1000000以下であることを確認する必要があります。

xrangeがsqrt(zrange)よりもはるかに大きい場合は、あなたものために、二つにあなたのふるい列を分割することができますがスキームをふるいオフセット。下位の配列は、2からsqrt(zrange)にわたります。上のものはxrangeからzrangeに及ぶでしょう。あなたの下の配列をふるい分け、それぞれの新しい素数が内側のループの内側で識別されるようになり、下の配列をその端までマーキングするだけでなく、上の配列もふるい分けます。各素数の開始オフセットは、iを計算し、下半分の場合と同じ手順で2*iを使用する必要があります。あなたの範囲がいくつかの素数よりも広い場合は、スピードの優位性が得られます（そうでなければ、オッズでの試行分割で十分です）。

evens > 2がとにかく素数でない場合、なぜそれらを配列内に表現し、空間の半分を無駄にするのでしょうか？それぞれiを奇数を表すものとして扱うことができます。2*i+1、したがっては、の配列を半分に圧縮します。

最終簡単なトリックだけではなくodds（すなわちcoprimes 2付き）、{ ... i+=2; ...}によってONをマークすることによって、同様に事前中3 の倍数を排除することですが、唯一の代わり{ ... i+=2; ... i+=4; ... }により、2と3でcoprimes 。また、OFFの素数の倍数> 3をマークする場合は、{ ... j+=2*i; ... j+=4i; ...}も使用してください。例えば、5*5, 5*7, 5*9, 5*11, ...にOFF5*9のマークを付ける必要はありません。3の倍数にONが最初に表示されていない場合は、