Project Euler Problem 58：螺旋質數比例低於 10% 的邊長

題目簡介

從 1 開始逆時針螺旋填數形成正方形。邊長為 7 時，對角線上 13 個數有 8 個質數（比例 ≈62%）。繼續擴展螺旋，求質數比例首次低於 10% 時的邊長。

規律分析

第 k 層（k≥1）正方形邊長 = 2k+1，右下角為奇數平方 (2k+1)^2。四條對角線上的新增數字為：

• a1 = (2k+1)^2 - 6k（左下）
• a2 = (2k+1)^2 - 4k（左上）
• a3 = (2k+1)^2 - 2k（右上）
• a4 = (2k+1)^2（右下，總是合數，非質數）

每層增加 3 個候選質數（除右下角）。累計質數個數 / 總對角線數（4k+1）< 0.1 時停止。

代碼實現

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i*i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int primeCount = 0;
    for (int k = 1; ; k++) {
        long long side = 2LL*k + 1;
        long long sq = side * side;
        long long cand[3] = {sq - 6*k, sq - 4*k, sq - 2*k};
        for (long long x : cand) if (isPrime(x)) primeCount++;
        int totalDiag = 4*k + 1;
        if (primeCount * 1.0 / totalDiag < 0.10) {
            cout << side << endl; // 邊長
            break;
        }
    }
    return 0;
}

結果

程序輸出邊長 26241（需驗證）。