如何在 Java 中有效率地檢查兩個平方數的和

1. 引言

在本簡短教程中，我們將探索一種高效的方法，用於判斷給定的整數n是否可以表示為兩個整數a和b的平方和。最基本的測試方法是窮舉法，但我們發現它在時間和記憶體方面效率低。因此，我們藉助初等數論原理，特別是費馬關於平方和的定理，發展出數學上嚴謹、速度更快、精度更高的解。

2. 費馬平方和定理

著名數學家皮埃爾·德·費馬提出了以下定理：

正整數n可以表示為兩個平方數和，當且僅當n的質因數分解不包含質數p奇次冪，其中p的形式為4k + 3 k為正整數。

讓我們透過幾個例子來理解這一點。當n = 19時，我們可以得到它的質因數分解為 19 + 1。質數是 19，它可以寫成 4(4) + 3 的形式。它的指數是 1（奇數）。根據定理，我們不能把 19 寫成兩個平方數的和。

現在，我們取n=225 。它的質因數分解是3².5² 。質數是 3，可以寫成 4(0) + 3。它的指數是 2（偶數）。因此，根據定理，我們可以把 225 寫成兩個平方數和 ( 12² + 9² )。

3. 實施

接下來，我們實作NumberAsSumOfTwoSquares()方法，以測試是否可以將給定的整數表示為兩個平方數的和：

public static boolean isSumOfTwoSquares(int n) {

 private static final Logger LOGGER = LoggerFactory.getLogger(NumberAsSumOfTwoSquares.class);

 ...

 };

關鍵在於避免進行完全質因數分解，而是專注於求出4k + 3質因數的指數。首先，我們快速檢查輸入n是否為負數。此時，我們會記錄一條警告訊息並傳回false:

if (n < 0) {

 LOGGER.warn("Input must be non-negative. Returning false for n = {}", n);

 return false;

 }

接下來，我們檢查平凡情況n = 0因為我們可以將 0 表示為兩個平方數和(0 2 + 0 2 ) ，所以我們回傳true ：

if (n == 0) {

 return true;

 }

接下來，我們檢查輸入n是否為偶數，並透過連續除法將其減少到奇數：

while (n % 2 == 0) {

 n /= 2;

 }

然後，我們遍歷直到n的平方根的所有奇數i (3, 5, 7, …) ，並檢查每個i是否是n的因子。如果是，我們透過統計它整除n次數來找到它的指數（記為count ）。然後，如果因子 i 的形式為4k + 3 ，且count為奇數，則傳回false ，因為這違反了規則：

for (int i = 3; i * i <= n; i += 2) {

 int count = 0;

 while (n % i == 0) {

 count++;

 n /= i;

 }

 if (i % 4 == 3 && count % 2 != 0) {

 LOGGER.debug("Failing condition: factor {} (form 4k+3) has odd exponent {}", i, count);

 return false;

 }

 }

循環結束後，剩餘的n > 1的值也是一個質因數。因此，我們進行最終檢查：如果剩餘的n是4k + 3的形式，則其指數為奇數（1），如果是，則記錄警告並傳回false 。

if (n % 4 == 3) {

 LOGGER.debug("Failing condition: remaining factor {} is of form 4k+3", n);

 return false;

 }

如果到達末尾，則傳回true因為n已通過所有檢查：

return true;

4. 驗證

讓我們使用JUnit測試上面部分的程式碼：

@Test

 @DisplayName("Given input number can be expressed as a sum of squares, when checked, then returns true")

 class NumberAsSumOfTwoSquaresUnitTest {

 ...

 }

我們使用方法givenNumberIsSumOfSquares_whenCheckIsCalled_thenReturnsTrue().這裡，程式傳回true ，表示我們可以將輸入的整數n表示為兩個整數的平方和：

givenNumberIsSumOfSquares_whenCheckIsCalled_thenReturnsTrue() {

 }

這裡，每次運行的輸入都是n ，它可以表示為兩個整數平方和。當我們呼叫方法 ` NumberAsSumOfTwoSquares(n)時，如果該方法每次呼叫都傳回true則斷言assertTrue 。例如， n=18可以表示為 18= 3² + 3² ，因此我們的程式將傳回true,測試運行通過：

assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(0));

 assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(8));

 assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(50));

 assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(45));

 assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(18));

5. 結論

在本文中，我們研究了一個經典的數論問題，並用 Java 有效地解決了它。我們應用費馬關於兩個平方數總和的定理，開發了一種檢查一個數的質因數的演算法，而不是依賴緩慢的暴力搜尋。

與往常一樣，本文的完整程式碼可在 GitHub 上找到。