您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 程式設計入門

Java 連續奇數合數演算法：暴力解法與效能分析

編輯：Java 程式設計入門

問題描述

尋找最小的正奇數 a，使得連續 n 個奇數 a, a+2, a+4, ..., a+2(n-1) 全部為合數（非質數）。

暴力解法邏輯

從 1 開始遍歷奇數
對每個候選數 a，檢查連續 n 個奇數是否全為合數
合數判定：存在 2 到 √n 之間的因數
找到第一個滿足條件的 a 即為答案

核心程式碼


import java.util.*;

public class ConsecutiveOddComposites {
    
    /** 判斷是否為合數 */
    public static boolean isComposite(int num) {
        if (num < 4) return false;  // 1,2,3 非合數
        int sqrt = (int) Math.sqrt(num);
        for (int i = 2; i <= sqrt; i++) {
            if (num % i == 0) return true;
        }
        return false;
    }
    
    /** 尋找連續 n 個奇數合數的最小起始值 */
    public static int findMinStart(int n) {
        for (int a = 1; ; a += 2) {  // 只檢查奇數
            boolean allComposite = true;
            for (int k = 0; k < n; k++) {
                if (!isComposite(a + 2 * k)) {
                    allComposite = false;
                    break;
                }
            }
            if (allComposite) return a;
        }
    }
    
    public static void main(String[] args) {
        for (int n = 1; n <= 10; n++) {
            long start = System.currentTimeMillis();
            int result = findMinStart(n);
            long elapsed = System.currentTimeMillis() - start;
            System.out.printf("n=%d: a=%d (耗時 %d ms)%n", n, result, elapsed);
        }
    }
}

執行結果（部分）


n=1: a=9 (耗時 0 ms)
n=2: a=25 (耗時 0 ms)
n=3: a=91 (耗時 0 ms)
n=4: a=115 (耗時 1 ms)
n=5: a=115 (耗時 1 ms)
n=6: a=115 (耗時 1 ms)
n=7: a=525 (耗時 1 ms)
n=8: a=525 (耗時 1 ms)
n=9: a=889 (耗時 1 ms)
n=10: a=1131 (耗時 1 ms)
n=11: a=1329 (耗時 1 ms)
n=12: a=1329 (耗時 1 ms)
...
n=26: a=31399 (耗時 5 ms)
...
n=36: a=155923 (耗時 92 ms)
...
n=77: a=17051709 (耗時 86082 ms)
...
n=90: a=20831325 (耗時 34772 ms)

效能分析與優化方向

時間複雜度

外層循環：~O(answer)
內層合數檢查：O(n × √a)
總體：指數級增長，n=77 耗時 86 秒，n=90 耗時 35 秒（結果較小）

優化策略

1. 質數篩法預計算


// 埃拉托斯特尼篩法預先標記合數
int LIMIT = 100_000_000;
boolean[] isComposite = new boolean[LIMIT + 1];
for (int i = 2; i * i <= LIMIT; i++) {
    if (!isComposite[i]) {
        for (int j = i * i; j <= LIMIT; j += i) {
            isComposite[j] = true;
        }
    }
}
// 查詢 O(1)

2. 跳過已知質數區間


// 維護質數表，遇到質數直接跳過其所在的連續區間
List primes = sieve(limit);
for (int a = 1; ; a += 2) {
    if (isPrime(a)) continue;  // 起始點不能是質數
    // 檢查...
}

3. 滑動窗口避免重複檢查


// 記錄連續合數長度
int consecutive = 0;
for (int a = 1; ; a += 2) {
    if (isComposite(a)) {
        consecutive++;
        if (consecutive >= n) return a - 2 * (n - 1);
    } else {
        consecutive = 0;
    }
}

4. 數學洞察：中國剩餘定理構造

對於給定 n，可構造同餘方程組使每個數都有小質因數：


a ≡ 0 (mod 3)
a+2 ≡ 0 (mod 5)
a+4 ≡ 0 (mod 7)
...
// 解得最小正解即為答案（不一定是最小，但提供上界）

完整優化版程式碼


import java.util.*;

public class OptimizedSearch {
    private static final int MAX_LIMIT = 200_000_000;
    private static boolean[] composite;
    
    public static void main(String[] args) {
        System.out.println("預計算合數表...");
        long t0 = System.currentTimeMillis();
        sieve();
        System.out.printf("預計算完成，耗時 %d ms%n", System.currentTimeMillis() - t0);
        
        for (int n = 1; n <= 100; n++) {
            long start = System.currentTimeMillis();
            int result = findMinStartFast(n);
            long elapsed = System.currentTimeMillis() - start;
            System.out.printf("n=%3d: a=%10d (查詢 %d ms)%n", n, result, elapsed);
        }
    }
    
    static void sieve() {
        composite = new boolean[MAX_LIMIT + 1];
        for (int i = 2; i * i <= MAX_LIMIT; i++) {
            if (!composite[i]) {
                for (int j = i * i; j <= MAX_LIMIT; j += i) {
                    composite[j] = true;
                }
            }
        }
        composite[0] = composite[1] = true;
    }
    
    static int findMinStartFast(int n) {
        int consecutive = 0;
        for (int a = 1; a <= MAX_LIMIT; a += 2) {
            if (composite[a]) {
                consecutive++;
                if (consecutive >= n) return a - 2 * (n - 1);
            } else {
                consecutive = 0;
            }
        }
        return -1;  // 超出限制
    }
}