給大整數 K（< 10¹⁰⁰，字符串輸入）與上限 L（< 10⁶）。求 K 的最小素因子 p（p < L），輸出 BAD p；若無此類因子，輸出 GOOD。
primes[]。關鍵優化：每個合數僅被其最小素因子篩一次（for (j=0; j）。 rem = (rem * 10 + digit) % p。或原碼做法：每 3 位切分（基數 1000），rem = (rem * 1000 + chunk) % p，減少循環次數。rem == 0 即為答案。for (int i = 2; i < L; ++i) {
if (!vis[i]) primes[cnt++] = i;
for (int j = 0; j < cnt && i * primes[j] < L; ++j) {
vis[i * primes[j]] = 1;
if (i % primes[j] == 0) break; // 保證每合數僅被最小素因子篩一次
}
}bool divisible(const char* K, int p) {
int rem = 0, len = strlen(K);
for (int i = 0; i < len; ) {
int chunk = 0, d = 0;
while (i < len && d < 3) chunk = chunk * 10 + (K[i++] - '0'), ++d;
rem = (rem * 1000 + chunk) % p;
}
return rem == 0;
}O(L)，L ≤ 10⁶ 约 7.8 萬個素數。O(|K|/3)，最壞總 O(π(L) × |K|) ≈ 7.8×10⁴ × 33 ≈ 2.6×10⁶ 操作，極快。本題結合「線性篩素數」與「大整數模運算」。線性篩保證 O(L) 時間且每合數僅處理一次；大整數模運算利用模運算分配律逐位計算，基數 1000 優化常數。模板價值極高，適用於所有「大數找小因子」問題。
