Java 判斷 101-200 間的素數並統計個數

素數判斷算法

對數 n，只需檢查 2 ~ sqrt(n) 能否整除。優化：先除 2，再從 3 步長 2 試除奇數。

代碼實現

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

    public static void main(String[] args) {
        int count = 0;
        for (int i = 101; i <= 200; i++) {
            if (isPrime(i)) {
                System.out.print(i + " ");
                count++;
            }
        }
        System.out.println("\n共 " + count + " 個素數");
    }
}

輸出結果

101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
共 21 個素數

進階：埃拉托斯特尼篩法 (求區間素數更高效)

boolean[] isPrime = new boolean[201];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= 200; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= 200; j += i) isPrime[j] = false;
    }
}
for (int i = 101; i <= 200; i++) if (isPrime[i]) { /* collect */ }

篩法預處理 O(N log log N)，查詢 O(1)，適合多次區間查詢。