template <typename T>
bool primejudge(T n)
{
    if (n < 2)
        return false;
    else if (n == 2)
        return true;
    else if (n % 2 == 0)
        return false;
    double sqrtn = sqrt(n);
    for (T i = 3; i < sqrtn + 1; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
        i++;
    }
    return true;
}
/*
0~nまでのn+1個のそれぞれの整数が素数であるかを判定
計算量はO(nloglogn)
n<=10^6程度なら愚直に素数判定しても間に合うが、n<=10^7程度だとエラストネスの篩が必要
*/
template <typename T>
vector<bool> Eratosthenes(T n)
{
    vector<bool> ret(n + 1, true);
    if (n >= 0)
        ret[0] = false;
    if (n >= 1)
        ret[1] = false;
    for (T i = 2; i * i <= n; i++)
    {
        if (!ret[i])
            continue;
        for (T j = i * i; j <= n; j += i)
        {
            ret[j] = false;
        }
    }
    return ret;
}