AcWing 4874. 约数
原题链接
中等
作者:
清秋十三
,
2023-03-23 10:55:39
,
所有人可见
,
阅读 156
超时;解决:不用动态数组vector不用cin cout
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
using namespace std;
const int mon = 1e6;//筛选从2-mon之间的素数(题目是到10的12次方,取根号到6次方就行)
int is_prime[mon]; //判断是否为素数
int prime[mon],k=0;//素数加入这个数组
void get_prime(int mon)
{
for (int i = 2; i <= mon; i++) is_prime[i] = 1;//先认为从2到mon都是素数
for (int i = 2; i <= mon; i++) {
if (is_prime[i]) prime[k++] = i; //如果判断数组is_prime是1就是素数,加入prime数组
for (int j = 0; prime[j] * i < mon; j++) {
//for(int j = 0;j < prime.size(); j++){/*这里j是从0开始*/
is_prime[i * prime[j]] = 0; //将非素数对应判断数组的值置为0 例如:2*2=4,is_prime[4]就是非素数
/*最重要的if*/
if (!(i % prime[j])) break; //如果i是prime[i]的倍数,那就不是素数
}
}
}
int main()
{
get_prime(mon);//储存从2-mon之间的素数
//cout << prime.size();
int n;
long long int x;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", &x) ;
int t = sqrt(x);//例如x=25,t就是5,后面再判断5是不是素数
if ((long long)(t)*t == x && is_prime[t] == 1) //判断是否是素数的平方,并且判断函数是1,这里is_prime内是t
printf("YES\n");
else
printf("NO\n");
}
return 0;
}