建立视频网站要多少钱,天津南昌网站建设,网页综合设计,临沂网站建设兼职我们知道#xff0c;质数是具有两个不同正除数的正整数。同样#xff0c;我们把正整数 t t t 称为质数。Т-质数#xff0c;如果 t t t 恰好有三个不同的正除数。
给你一个由 n 个正整数组成的数组。请判断其中每个整数是否为 Т-prime。
输入 第一行包含一个正整数 n …我们知道质数是具有两个不同正除数的正整数。同样我们把正整数 t t t 称为质数。Т-质数如果 t t t 恰好有三个不同的正除数。
给你一个由 n 个正整数组成的数组。请判断其中每个整数是否为 Т-prime。
输入 第一行包含一个正整数 n ( 1 ≤ n ≤ 1 0 5 ) n ( 1 ≤ n ≤ 10^5 ) n(1 ≤ n ≤ 105)显示数组中有多少个数字。下一行包含 n n n 个空格分隔的整数 x i ( 1 ≤ x i ≤ 1 0 1 2 ) x_i ( 1 ≤ x_i ≤ 10^12 ) xi(1 ≤ xi ≤ 1012)。 请不要使用 %lld 指定符在 С 中读写 64 位整数。建议使用 cin、cout 流或 %I64d指定符。
输出 打印 n n n 行如果数字 x i x_i xi 是 Т-prime则第 i i i 行应包含是(不带引号)如果数字 x i x_i xi 不是 Т-prime则第 i i i 行应包含否(不带引号)。 虽然标签有模拟但是这是纯纯的数论题。 首先我们知道一个质数的因数只有1和他自己那么一个质数的平方数的因数就只有1和他自己还有他开平方的数。
知道了这一点就可以直接开始写出求约数个数的函数只要按照是质数并且是一个平方数判断就可以。
代码
#includeiostream
#includecmath
using namespace std;
const int N 1e6 10;int primes[N];
int cnt;
int st[N];void get_primes(){for(int i 2;i N;i){if(!st[i])primes[cnt] i;for(int j 0;primes[j] N/i;j){st[primes[j]*i] 1;if(i % primes[j] 0)break;}}
}int main(){get_primes();int n;cin n;while(n--){long long a;cin a;long long t (long long)sqrt(a);//这里要判断t*t是否等于a因为sqrt得来的t有可能不是a的开根if( !st[t] t*t a t 1)cout YES\n;else cout NO\n;}return 0;
}
