forループでいっぱいになったJavaコードをさらに最適化

Question

私は、ギャップがある与えられたlongに等しい2つの素数を返し、それらの間に他の素数を持たないコードを書いた。数が2つの数字

public static boolean repeatedIsPrime(long x, long y) { 
    for(long i=x; i<=y; i++) { 
     if(isPrime(i)) { 
      return true; 
     } 
    } 
return false; 
} 

間の素数があるのか​​どうかをチェックするために

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

素数であるかどうかをチェックするために

public static long[] firstGap(int gap, long lLimit, long uLimit) { 
    for(long i=lLimit; i<=uLimit; i++) { 
     for(long j=i+1; j<=uLimit; j++) { 
      if(isPrime(i) && isPrime(j) && j-i==gap && !repeatedIsPrime(i+1,j-1)) { 
       return new long[]{i,j}; 
      } 
     } 
    } 
return null; 
} 

：

これらは私がこれまでに作った方法があります

私がこれまで行ってきたことは、ループインデックスをintとして持っていたのですが、その後、私は損失のある変換をしていました。メソッドの呼び出しをeducingが、私はそれを行う方法を見つけることができません。私が今までに作った唯一の改善点は、私が何も持っていない以外の値の不必要な格納と割り当てを取り除いたことです。では、コードをさらに最適化するにはどうすればよいですか？

Answer 1

あなたは、次のコードを使用することができます

public static long[] firstGap(int gap, long lLimit, long uLimit) { 
    for(long i=lLimit; i<=uLimit; i++) { 
     if(isPrime(i)) { 
      long j = gap + i; 
      if (isPrime(j) && !repeatedIsPrime(i + 1, j - 1)) { 
       return new long[]{i, j}; 
      } 
     } 
    } 
    return null; 
} 

まず、isPrime（i）は== falseを、他のチェックはいかなる意味を持っていない場合。第二に、あなたが唯一のJを使用しているため、for(long j=i+1; j<=uLimit; j++)は、削除することができる（ときJI ==ギャップ）

Answer 2

1. 内部ループを削除します！ `（isPrime（i）が& & isPrimeは、（i）は、ギャップを+場合& & repeatedIsPrime （i + 2、i + gap-2）return new long [] {i、j}
2. lLimitとuLimitが奇数であり、偶数をチェックする意味がないことを確認してください。
3. プライムをチェックするとき、nの平方根まで実行
4. HashMap < Long、Boolean>を使用すると、一度同じ番号を確認しますが、移動するときに最小番号を削除する必要があります
5. スマートな素数性テストを使用します。フェルマーテストhttps://en.wikipedia.org/wiki/Primality_test#Fermat_primality_test速いisPrime（i）