#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>

// 快速幂算法，用于模幂运算
long long mod_pow(long long base, long long exponent, long long modulus) {
    long long result = 1;
    base %= modulus;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        exponent >>= 1;
        base = (base * base) % modulus;
    }
    return result;
}

// 米勒-拉宾素性测试
bool miller_rabin_test(long long n, int iterations) {
    if (n == 2) return true;
    if (n <= 1 || n % 2 == 0) return false;

    // 找到n-1的二进制表示中1的个数
    long long s = n - 1;
    int count = 0;
    while (s > 0) {
        if (s % 2 == 1) count++;
        s >>= 1;
    }

    // 选择一个小于n的随机数a
    srand(static_cast<unsigned int>(time(0)));
    bool is_prime = true;
    for (int i = 0; i < iterations; ++i) {
        long long a = rand() % (n - 1) + 1;
        long long x = mod_pow(a, s, n);

        if (x == 1 || x == n - 1) continue;

        // 进行count次平方运算
        for (int j = 0; j < count - 1; ++j) {
            x = mod_pow(x, 2, n);
            if (x == n - 1) {
                is_prime = true;
                break;
            }
        }

        if (is_prime) continue;

        // 如果x不是n-1，那么n不是质数
        is_prime = false;
        break;
    }

    return is_prime;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    long long n;
    int iterations = 20; // 根据经验，20次迭代通常足够

    while (std::cin >> n) {
        std::cout << (miller_rabin_test(n, iterations) ? "Y" : "N") << std::endl;
    }
    return 0;
}

题目

判定输入的数是不是质数。

输入

若干行，一行一个数X。 行数不超过 $10^5$。

输出

对于输入的每一行，如果 x 是质数输出一行Y，否则输出一行N。

样例

输入数据 1

1
2
6
9
666623333

输出数据 1

N
Y
N
N
Y

数据范围

1≤x≤$10^9*10^9$。