完全数を見つけるのを速くすることはできますか？配列と別のアルゴリズムで高速化しようとしましたが、どれも高速化できませんでした。
public class Perfect{
static long perfectNumber;
static long startTime = System.nanoTime();
static long endTime;
static long mersenne;
public static void main(String[] args) {
long p = 2;
while (p < 32) {
if( p % 2 == 0&&p!=2){
p++;
}
else{
if (isPrime(p) == true) {
mersenne = (long) (Math.pow(2, p) - 1);
if (isPrime(mersenne) == true) {
perfectNumber = (long) Math.pow(2, (p - 1)) * mersenne;
System.out.println(perfectNumber);
}
}
p++;
}
}
endTime = System.nanoTime();
System.out.println("Time: " + (endTime - startTime) + "ns"
);
}
private static boolean isPrime(long testPrime) {
for (long i = 3; i < Math.sqrt(testPrime); i += 2) {
if (testPrime % i == 0) {
return false;
}
}
return true;
}
}
あなたが行うことができるいくつかのマイナーな改善があります-おそらくどれも実行時間に何の違いもありません：
p % 2すると除算が発生する可能性がありp & 1ます。除算は行われないため、数分の1速くなるはずです。Math.pow(2,x)は2 << xすべての場合に同等であり、はるかに高速である可能性があります。これらの些細でおそらく時期尚早な最適化とは別に、最適化を試みる前に、計算を数百回実行し、平均時間をとる必要があります。
ところで-使用nanotimeしているからといって、ナノ秒の解像度が得られているわけではありません-それからはほど遠いです。
また-
ウィキペディアの記事が指摘しているように、そこに記載されている一般的なバイナリパターンを列挙することで、計算の多くを回避できます。
for ( int i = 0; i < 10; i++ ) {
long q = ((1 << (i+2)) - 1) << (i+1);
// Printing BigIntegers in binary is easy.
BigInteger bq = BigInteger.valueOf(q);
System.out.println(q+" = "+bq.toString(2));
}
6 = 110
28 = 11100
120 = 1111000
496 = 111110000
2016 = 11111100000
8128 = 1111111000000
32640 = 111111110000000
130816 = 11111111100000000
523776 = 1111111111000000000
2096128 = 111111111110000000000
明らかに、あなたはまだそれらをテストする必要がありますが、あなたはほとんど同じくらい多くをテストする必要はありません。
また、さらに一歩進めたいBigInteger場合は、次のようなものから始めることができます。
for ( int i = 0; i < 10; i++ ) {
BigInteger p = BigInteger.ONE.shiftLeft(i+2).subtract(BigInteger.ONE).shiftLeft(i+1);
System.out.println(p.toString(10)+" = "+p.toString(2));
//long q = ((1 << (i+2)) - 1) << (i+1);
//BigInteger bq = BigInteger.valueOf(q);
//System.out.println(" "+bq.toString(10)+" = "+bq.toString(2));
}
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加