#52084: c++解(speed)
11155088@gs.hs.ntnu.edu.tw
(ace1110)
學校
:
不指定學校
編號 : 298370
來源 : [118.169.28.170]
最後登入時間 ：
2025-09-24 21:58:03
#include <iostream>
#include <cmath>
using bigint = unsigned long long;
bool is_prime(bigint num) {
// 跳過2/3的倍數
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0 || num % 3 == 0) return false;
bigint divisor = 5; // 從 5 開始
bigint step = 2; // 步長交替 +2, +4
while (divisor <= num / divisor) { // 避免乘法溢出
if (num % divisor == 0) return false;
divisor += step;
step = 6 - step; // +2 <-> +4 交替
}
return true;
}
int main() {
bigint len;
std::cin >> len;
for (bigint i = 0; i < len; ++i) {
bigint number;
std::cin >> number;
std::cout << (is_prime(number) ? 'Y':'N') << std::endl;
}
return 0;
}