Perfect Pth Powers

Description

We say that x is a perfect square if, for some integer b, x = b2. Similarly, x is a perfect cube if, for some integer b, x = b3. More generally, x is a perfect pth power if, for some integer b, x = bp. Given an integer x you are to determine the largest p such that x is a perfect pth power.

Input

Each test case is given by a line of input containing x. The value of x will have magnitude at least 2 and be within the range of a (32-bit) int in C, C++, and Java. A line containing 0 follows the last test case.

Output

For each test case, output a line giving the largest integer p such that x is a perfect pth power.

Sample Input

17

1073741824

25

0

Sample Output

1

30

2

题意描述：

求一个数的最大次方数。（已知n，求x；n=a^x）

解题思路：

从网上看了有两种思路：

一种是利用pow()函数直接循环枚举找到符合条件的数，不过要注意精度问题：

x=(int)(pow(n*1.0,1.0/i)+0.1); 

y=(int)(pow(x*1.0,1.0*i)+0.1);

另一种是分解质因数，将n分解为多个素数的次方乘积。求着多个素数的次方的最大公约数，即为所求的x；注意若n为负数情况，若n为负数，且得到的最大公约数为偶数，将偶数除以二，直到得到奇数即为所求x（因只有负数的奇数次方才为负数）。

粘一个别人写的枚举的https://blog.csdn.net/lianai911/article/details/39494291

思路：p从31到1遍历，求n的p次开方，转为int型的t，再求t的p次方，转为int型的x

若x和n相等，则求得的p为最大值，break出循环

注意：求n的p次开方用pow()求，因为pow()函数得到的为double型，而double型数据

精度问题，比如4可表示为3.99999……或4.0000001，所以转为int型时+0.1

#include<stdio.h>
#include<math.h>
 
int main()
{
    int n;
    while(~scanf("%d",&n) && n)
    {
        if(n > 0)
        {
            for(int i = 31; i >= 1; i--)
            {
                int t = (int)(pow(n*1.0,1.0/i) + 0.1);
                int x = (int)(pow(t*1.0,1.0*i) + 0.1);
                if(n == x)
                {
                    printf("%d\n",i);
                    break;
                }
            }
 
        }
        else
        {
            n = -n;
            for(int i = 31; i >= 1; i-=2)
            {
                int t = (int)(pow(n*1.0,1.0/i) + 0.1);
                int x = (int)(pow(t*1.0,1.0*i) + 0.1);
                if(n == x)
                {
                    printf("%d\n",i);
                    break;
                }
            }
        }
    }
    return 0;
}

分解质因数：

#include<stdio.h>
#include<math.h>
#include<string.h>
# define N 1000000
int isprime[N];
int prime[N];
int gcd(int x,int y)
{
	int t;
	if(y>x)
		return gcd(y,x); 
	if(y==0)
		return x;
	t=x%y;
	return gcd(y,t);
}
int main()
{
	long long n;
	int m,f,i,j,num,ans,cut,flag;
	memset(isprime,0,sizeof(isprime));
	isprime[0]=isprime[1]=1;
	num=1;
	for(i=2;i<=N;i++)//筛法将是素数的依次存入数组 
		if(isprime[i]==0)
		{
			prime[num++]=i;
			for(j=2*i;j<=N;j=j+i)//筛掉素数的整数倍，标记为一 
				isprime[j]=1;
		}
	while(scanf("%lld",&n))
	{
		if(n==0)
			break;
		flag=0;
		if(n<0)
		{
			flag=1;
			n=-n;
		}
		ans=0;
		i=0;
		while(i<num-1&&n>1)
		{
			
			i++;
			cut=0;
			while(n%prime[i]==0)
			{
				n=n/prime[i];
				cut++;//统计次方数 
				
			}
			ans=gcd(ans,cut);
		}
		if(n!=1)
			ans=1;
		if(flag==1)
		{
			while(ans%2==0)
				ans=ans/2;
		}
		printf("%d\n",ans);
		
	}
	return 0;
}