此数据范围可以使用费马小定理求解。

费马小定理会造成一个伪素数的情况，我对此的解决方式是：多随机几个数多判断几次（我这里是 5 次）。

费马小定理判断模块使用快速幂即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long

// 快速幂
ll quickpow(ll a, ll b, ll mod)
{
	ll ans = 1 % mod;
	while (b)
	{
		if (b & 1)
			ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
// 费马小定理
bool isPrime(ll n, int k = 5)
{
  // 特判 1，2，3，偶数，3 倍数。
    if (n <= 1) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    srand(time(0)); // 随机
    for (int i = 0; i < k; i++)
	{
        ll a = rand() % (n - 3) + 2;
        
        if (quickpow(a, n - 1, n) != 1)
            return false;
    }
    return true;
}

ll t, n;

int main()
{
	while (cin >> n)
	{
	    if (isPrime(n))
	        cout << "Y" << "\n";
	    else
	        cout << "N" << "\n";
	}
    return 0;
}