数论 CF230B T-primes

CF230B T-primes

我们知道质数是只有两个不同的正数因数的正整数。相似的，我们把一个正整数 t 叫做 T质数，如果 t 恰好有三个不同的正整数因数。

你被给了一个含有 n 个正整数的数组。你要给其中所有的数判断它是否是 T质数。

可以知道一个质数的完全平方数有且只有三个因子。

然后这题就水了。

线性筛出1到$\sqrt{a_i} $的素数，判断就行了。

code:

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#define int long long

using namespace std;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

int n,tot;

int a[100017];

int prime[1000017];

int isprime[1000017];

void Euler(){

	memset(isprime,1,sizeof isprime);

	isprime[1]=0;

	for(int i=2;i<=1000000;i++){

		if(isprime[i])

			prime[++tot]=i;

		for(int j=1;j<=tot&&i*prime[j]<=1000000;j++){

			isprime[i*prime[j]]=0;

			if(i%prime[j]==0)break;

		}

	}

}

signed main(){

	n=read(); Euler();

	for(int i=1;i<=n;i++)a[i]=read();

	for(int i=1;i<=n;i++){

		int tmp=sqrt(a[i]+0.5);

		if(isprime[tmp]){

			if(tmp*tmp==a[i])puts("YES");

			else puts("NO");

		}

		else puts("NO");

	}

	return 0;

}

巴特西

数论 CF230B T-primes

CF230B T-primes

最新文章

热门文章