素數距離問題：尋找最近素數與距離計算的C語言實現

素數距離問題：尋找最近素數與距離計算的C語言實現

給定多組整數 M (0 < M < 1,000,000)，對每個 M 輸出距離最近的素數 A 及距離 B。若 M 本身為素數，輸出 M 0；左右等距時取左側（較小）素數。

算法步驟

1. isPrime(n)：試除法判斷素數，i*i <= n 優化。
2. 若 M 為素數直接輸出。
3. 否則雙向搜索：numUp 遞增找下一素數，numDown 遞減找上一素數（>0）。
4. 計算距離 deltUp、deltDown，比較取小；numDown==0 時只能取右側。

完整代碼

int isPrime(int num) {
    if (num == 1) return 0;
    for (int i=2; i*i<=num; i++) if (num%i==0) return 0;
    return 1;
}

int main() {
    int n, num, numUp, numDown, deltUp, deltDown;
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &num);
        if (isPrime(num)) { printf("%d 0\n", num); continue; }
        numUp = numDown = num;
        while (!isPrime(numUp)) numUp++;
        while (!isPrime(numDown) && numDown>0) numDown--;
        deltUp = numUp - num; deltDown = num - numDown;
        if (numDown==0 || deltUp < deltDown) printf("%d %d\n", numUp, deltUp);
        else printf("%d %d\n", numDown, deltDown);
    }
    return 0;
}

時間複雜度約 O(N * sqrt(M))，滿足 N<=10000, M<1e6 限制。