NYOJ 24 素數距離問題：雙向搜索最近素數

算法邏輯

對每個查詢數 M (1 ≤ M < 1e6)：

1. 若 M 為素數，輸出 M 0。
2. 否則雙向擴展距離 d = 1,2,3...（奇數 M 從 d=0 開始，偶數從 d=1 保證檢查奇數）：
   • 先檢查 M-d 是否為素數，是則輸出 M-d d（優先左側）。
   • 再檢查 M+d，是則輸出 M+d d。
3. 特例 M=1：非素數，最近為 2，距離 1。

素數判定優化

試除法至 √x，預處理 2,3 為素數，偶數直接返回 false。查詢數 ≤ 10000，單次判定極快，無需篩法預處理。

Java 實現亮點

boolean is_prime(int x) {
    if (x < 2) return false;
    if (x < 4) return true; // 2,3
    for (int i=2; i*i<=x; ++i)
        if (x%i==0) return false;
    return true;
}
// 主循環
int d = (m%2==0)?1:0;
if (m==1) { print "2 1"; continue; }
while (true) {
    if (is_prime(m-d)) { print m-d, d; break; }
    if (is_prime(m+d)) { print m+d, d; break; }
    d += 2;
}

距離步長 +2 保證只檢查奇數，效率提升一倍。