摘要：
【编程题】超级素数幂时间限制：1秒空间限制：32768K如果一个数可以表示为p^q，p是素数，q是大于1的正整数，则称为超级素数幂。现在我们给出一个正整数n。如果n是超素数幂，我们需要找到相应的p，q。
[编程题] 超级素数幂
时间限制：1秒
空间限制：32768K
如果一个数字能表示为p^q(^表示幂运算)且p为一个素数,q为大于1的正整数就称这个数叫做超级素数幂。现在给出一个正整数n,如果n是一个超级素数幂需要找出对应的p,q。
输入描述:
输入一个正整数n(2 ≤ n ≤ 10^18)
输出描述:
如果n是一个超级素数幂则输出p,q,以空格分隔,行末无空格。 如果n不是超级素数幂，则输出No
输入例子:
27
输出例子:
3 3
解题思路：枚举q，对于每个q求p，然后判断求出的p是否为整数且为素数，如果是，则输出，不是则继续查找，查找完成还没有结果，则输出NO
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 5 /*素数判定函数*/ 6 bool isPrime( int n ){ 7 if( n <= 1 ){ 8 return false; 9 } 10 for( int i = 2; i <= sqrt(n); ++i ){ 11 if( n%i == 0 ){ 12 return false; 13 } 14 } 15 return true; 16 } 17 18 int main() 19 { 20 long long int n; 21 while( cin>>n ){ 22 int max_q = log2(n); 23 int flag = 0; 24 for( int q = 2; q <= max_q; ++q ){ 25 double p = pow( n, 1.0/q ); //p^q = n ——> p = n^(1/q) 26 if( p-int(p)==0 && isPrime( int(p) ) ){ //p^q = n ——> n开q次方后恰好得到素数p 27 cout<<int(p)<<" "<<q<<endl; 28 flag = 1; 29 break; 30 } 31 } 32 if( !flag ){//未找到满足条件的p,q 33 cout<<"No"<<endl; 34 } 35 } 36 return 0; 37 }