3053 - 最大完全平方因子

72

36

Hint

	

		72的完全平方因子有4 9 36 最大的必然是36了。
	

Solution C++

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const long long maxn=1000005;
const long long N=96000;
long long cnt;
long long n;
bool is_prime[maxn];
long long prime[maxn];
long long a[N];

void dabiao()
{
    is_prime[0]=is_prime[1]=1;
    long long  i;
    for(i=2;i<=maxn;i++)
    {
        is_prime[i]=0;
    }
    for(i=2;i<=maxn;i++)
    {
        if(is_prime[i]!=0)
        {
            continue;
        }
        for(long long  j=2*i;j<=maxn;j+=i)
        {
            is_prime[j]=1;
        }
    }
    cnt=0;
    for(long long i=2;i<=maxn;i++)
    {
        if(is_prime[i]==0)
        {
            prime[cnt++]=i;
        }
    }
}
int main()
{
   // freopen( "D.txt", "r", stdin );
   // freopen( "_D.txt", "w", stdout );
    dabiao();
    while(cin>>n)
    {
        long long res=1,tmp=0;
        for(long long i=0;i<cnt&&prime[i]<=n;i++)
        {
            if(n%prime[i]==0)
            {
                tmp=0;
                while(n%prime[i]==0)
                {
                    n/=prime[i];
                    tmp++;


                }
                if(tmp&1) tmp--;
                for(int j=0;j<tmp;j++) res*=prime[i];
            }
        }
        if(n!=1)
        {
            long long x=(long long )(sqrt(n+0.0));
            if(x*x==n)
            {
                res*=n;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}