CodeForces 230B

时间:2022-05-16 17:48:42   收藏:0   阅读:10

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!

原文:https://www.cnblogs.com/yocichen/p/15314061.html

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!