CodeForces 230B

CodeForces 230B

关键问题：

可被三个除数整除的数<=>素数的平方，其三个除数为(1,n,prims)。那么问题就转化为寻找【0，10^6】内的所有素数(筛法)的平方集，然后在集中搜索输入值；

我的解法

埃式筛法

#include <iostream>
#include <vector>
#include <set>
using namespace std;
 
// eratosthenes 埃式素数筛
// 可被三个除数整除的数<=>素数的平方，其三个除数为(1,n,prims)
void findPrims(set<long long>& tprims, vector<bool>& flags)
{
    flags[0] = flags[1] = false;
    for (long long i = 2; i < flags.size(); i++)
    {
        if (flags[i])
        {
            tprims.insert(i*i); // 素数平方即是T-Prims
            for (long long j = 2*i; j < flags.size(); j += i)
            {
                flags[j] = false; // 素数的倍数不是素数
            }
        }
    }
}
 
int main()
{
    int n;
    long long target;
    set<long long> tprims;
    vector<bool> flags(1000001, true);
    findPrims(tprims, flags);
    while(cin >> n)
    {
        while (n--)
        {
            cin >> target;
            if(tprims.find(target) != tprims.end()) 
                cout << "YES" << endl;
            else 
                cout << "NO" << endl;
        }
    }
}

注意
以上解法绝非是最佳算法，但保证Accept！