专栏首页奇妙的算法世界230B. T-primes (数论)

230B. T-primes (数论)

题意描述

We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we’ll call a positive integer t Т-prime, if t has exactly three distinct positive divisors.

You are given an array of n positive integers. For each of them determine whether it is Т-prime or not.

Input The first line contains a single positive integer, n (1 ≤ n ≤ 105), showing how many numbers are in the array. The next line contains n space-separated integers xi (1 ≤ xi ≤ 1012).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is advised to use the cin, cout streams or the %I64d specifier.

Output Print n lines: the i-th line should contain “YES” (without the quotes), if number xi is Т-prime, and “NO” (without the quotes), if it isn’t.

Examples input 3 4 5 6 output YES NO NO

题意

要想求只有三个因子的数,只需要判断这个数是否是素数的平方即可,可以先对所有的1~1e6的素数进行预处理,然后判断即可

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#pragma GCC optimize(2)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef long long LL;
const int N=5005;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int a[N];
int dp[N];
bool check(int k){
    if(k<2) return true;
    for(int i=2;i*i<=k;i++){
        if(k%i==0) return true;
    }
    return false;
}
int main(){
    IOS;
    set<LL> ans;
    for(int i=2;i<=1000000;i++){
        if(!check(i)){
            ans.insert((LL)i*i);
        }
    }
    int n;cin>>n;
    while(n--){
        LL x;cin>>x;
        if(ans.count(x)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • codeforce1178B (DP)

    Recall that string a is a subsequence of a string b if a can be obtained from b ...

    dejavu1zz
  • HDU 1867(kmp应用)

    Generally speaking, there are a lot of problems about strings processing. Now yo...

    dejavu1zz
  • codeforce 1263C (整除分块)

    这道题想了很久,打表发现了规律,每个值相同的块,最后一个因子都是n/(n/i),但找到规律以后不知道该如何实现,看了题解以后才发现这是一道整数分块的问题。 核...

    dejavu1zz
  • HDU 5652 India and China Origins(并查集)

    India and China Origins Time Limit: 2000/2000 MS (Java/Others)    Memory Limit:...

    ShenduCC
  • HDUOJ---2642Stars(二维树状数组)

    Stars Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/65536 K (Jav...

    Gxjun
  • Codeforces 833E Caramel Clouds

    E. Caramel Clouds time limit per test:3 seconds memory limit per test:256 megaby...

    Angel_Kitty
  • Android打造不一样的新手引导页面(一)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

    用户2965908
  • 洛谷P2863 [USACO06JAN]牛的舞会The Cow Prom

    ng the other ends of her ropes (if she has any), along with the cows holding the...

    attack
  • leetcode502. IPO

    Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

    眯眯眼的猫头鹰
  • 翻转瓷砖Fliptile(开关反转)- POJ 3279

    Farmer John knows that an intellectually satisfied cow is a happy cow who will g...

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券