题目链接:https://cn.vjudge.net/problem/Gym-101490I
题目大意:给你一个整数,问你这个整数能不能表示成一个素数的k次方?
具体思路:对于每一个数,我们先判断他是不是素数,如果是素数的话,就一定可以。其次,我们看一下当前的这个数能不能唯一的素因数分解。
PS:因为题目数据量是1e9,我们不可能跑一个1e9的素数筛,这样的话肯定会超时,对于每一个进来的数,我们先判断他是不是素数,如果是素数的话,输出yes。否则,就跑1e6之前的素数,看能不能分解就可以了。
AC代码:
1 #include <iostream> 2 #include<stack> 3 #include<stdio.h> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #include<map> 8 #include<cstring> 9 using namespace std; 10 # define ll long long 11 const ll maxn = 1e6+100; 12 int prime[maxn]; 13 int vis[maxn]; 14 int num=0; 15 void prim() 16 { 17 for(ll i = 2; i < maxn; i++) 18 { 19 if(!vis[i]) 20 prime[++num] = i; 21 for(ll j = 1; j<=num ; j++) 22 { 23 if(i*prime[j]>=maxn) 24 break; 25 vis[i*prime[j]] = true; 26 if(i % prime[j] == 0) 27 break; 28 } 29 } 30 } 31 bool judge(int t) 32 { 33 if(t<=1) 34 return false; 35 for(int i=2; i<=sqrt(t); i++) 36 { 37 if(t%i==0) 38 { 39 return false; 40 } 41 } 42 return true; 43 } 44 int main() 45 { 46 prim(); 47 ll n; 48 scanf("%lld",&n); 49 ll flag=1; 50 if(n==1) 51 printf("no\n"); 52 else 53 { 54 ll tmp=n; 55 if(judge(tmp)) 56 { 57 printf("yes\n"); 58 } 59 else 60 { 61 int flag=1; 62 for(int i=1; i<=num; i++) 63 { 64 //cout<<i<<" "<<prim[i]<<endl; 65 if(n%prime[i]==0) 66 { 67 while(n%prime[i]==0) 68 n/=prime[i]; 69 // cout<<n<<endl; 70 if(n==1) 71 flag=0; 72 break; 73 } 74 } 75 if(flag) 76 printf("no\n"); 77 else 78 printf("yes\n"); 79 } 80 } 81 return 0; 82 }