進一步優化我的Java代碼充滿for-loops

我寫了一個代碼，返回兩個素數，其間隙等於給定的long，並且它們之間沒有其他素數。進一步優化我的Java代碼充滿for-loops

這是迄今爲止我所做的方法：

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; 
}

爲了檢查一個數是否爲素

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

爲了檢查是否有兩個數字

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

之間的質數

我到目前爲止所做的工作是將循環索引作爲int，但然後我會有一個有損轉換，接下來是r引發方法調用，但我找不到一種方法來做到這一點。到目前爲止，我所做的唯一改進就是刪除了一些不必要的存儲和賦值，除此之外我什麼都沒有。那麼我如何進一步優化我的代碼呢？

來源

2017-09-02 Helquin

您可以通過首先改進算法來大大提高此程序的速度。減少方法調用不會使代碼更快。 – pvg

您可以使用下面的代碼：

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）==假的，其他的檢查沒有任何意義。其次，for(long j=i+1; j<=uLimit; j++)可以刪除，因爲你只使用一名的J（當姬==間隙）

來源

2017-09-02 18:13:20

拆下內循環：`如果（isPrime（I）& & isPrime（1 +間隙）& & repeatedIsPrime （i + 2，i + gap-2）返回新的long [] {i，j}
確保lLimit和uLimit是奇數並加2作爲無意義來檢查偶數
檢查素數，運行直到n的平方根
可以使用HashMap < Long，Boolean>確保你只有檢查相同的號碼 - 但移動時必須刪除最小號碼
使用更智能的素性測試，例如，費馬測試https://en.wikipedia.org/wiki/Primality_test#Fermat_primality_test isPrime（i）

來源

2017-09-02 18:15:32 Alexander

進一步優化我的Java代碼充滿for-loops

回答

相關問題