Java算法：求100以內素數 (統計50-100間素數個數並輸出)

Java求素數經典實現：篩法、試除法優化、區間統計完整代碼

素數 (質數) 判定是算法入門必考。本文提供三種實現：試除法優化 (√n)、**埃拉托斯特尼篩法 (O(n log log n))**、**線性篩法 (O(n))**，並完成題目要求：統計 50-100 間素數個數並輸出。

方案一：試除法優化 (適合單數判定、小範圍)

判定 n 是否為素數：只需試除 2 到 √n。優化：先除2，再從3開始步長2 (只試奇數)。

public class PrimeTrialDivision {
    // 判定單個數是否為素數
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false; // 排除偶數
        for (int i = 3; i * i <= n; i += 2) { // 只試奇數，到 √n
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println("=== 100以內所有素數 ===");
        for (int i = 2; i <= 100; i++) {
            if (isPrime(i)) System.out.print(i + " ");
        }
        System.out.println();

        System.out.println("\n=== 50-100 間素數統計 ===");
        int count = 0;
        for (int i = 50; i <= 100; i++) {
            if (isPrime(i)) {
                System.out.print(i + " ");
                count++;
            }
        }
        System.out.println("\n素數個數: " + count); // 輸出: 10 (53,59,61,67,71,73,79,83,89,97)
    }
}

方案二：埃拉托斯特尼篩法 (適合範圍內所有素數，極快)

public class PrimeSieveEratosthenes {
    public static void main(String[] args) {
        int N = 100;
        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) { // 從 i*i 開始標記
                    isPrime[j] = false;
                }
            }
        }

        System.out.println("100以內素數:");
        for (int i = 2; i <= N; i++) if (isPrime[i]) System.out.print(i + " ");

        System.out.println("\n\n50-100 間素數:");
        int count = 0;
        for (int i = 50; i <= 100; i++) {
            if (isPrime[i]) { System.out.print(i + " "); count++; }
        }
        System.out.println("\n個數: " + count);
    }
}

方案三：線性篩法 (歐拉篩, O(n)，每個合數僅被最小質因子標記一次)

import java.util.ArrayList;
import java.util.List;

public class PrimeLinearSieve {
    public static void main(String[] args) {
        int N = 100;
        boolean[] isComposite = new boolean[N + 1];
        List primes = new ArrayList<>();

        for (int i = 2; i <= N; i++) {
            if (!isComposite[i]) primes.add(i);
            for (int p : primes) {
                if (i * p > N) break;
                isComposite[i * p] = true;
                if (i % p == 0) break; // 核心：保證每個合數只被最小質因子標記
            }
        }

        System.out.println("素數列表: " + primes);
        System.out.println("50-100 間: ");
        int count = 0;
        for (int p : primes) {
            if (p >= 50 && p <= 100) { System.out.print(p + " "); count++; }
        }
        System.out.println("\n個數: " + count);
    }
}

性能與適用場景對比

題目要求輸出結果驗證

50-100 間素數: 53 59 61 67 71 73 79 83 89 97
素數個數: 10

大數素數判定擴展 (N > 10⁹)

• Miller-Rabin 素性測試：概率算法，極快，工程級首選 (Java BigInteger.isProbablePrime(certainty) 內置實現)。
• Pollard's Rho：大整數分解算法，配合 Miller-Rabin。

總結

100以內素數用 試除法優化 代碼最簡潔；需全表或重複查詢用 埃氏篩；極大範圍或需質因子分解用 線性篩。掌握 i*i <= n 邊界優化、i += 2 奇數步長、篩法 i*i 起標記核心優化，是算法基本功。