首页 > 代码库 > hdu 5108 Alexandra and Prime Numbers

hdu 5108 Alexandra and Prime Numbers

http://acm.hdu.edu.cn/showproblem.php?pid=5108

找出最大质因子就可以。

技术分享
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define ll long long 5 #define N 100000 6 using namespace std; 7  8 ll n; 9 10 11 int main()12 {13     while(scanf("%lld",&n)!=EOF)14     {15         ll m=n;16         if(n==1)17         {18             printf("0\n");19             continue;20         }21         bool flag=false;22         for(int i=2; i*i<=n; i++)23         {24             if(n%i==0)25             {26                 flag=true;27                 break;28             }29         }30         if(!flag)31         {32             printf("1\n");33             continue;34         }35         ll max1=2;36         for(int i=2; i*i<=n; i++)37         {38             if(n%i==0)39             {40                  if(max1<i) max1=i;41                  while(n%i==0) n/=i;42             }43         }44         if(n>1)45         {46             if(max1<n)47             {48                 max1=n;49             }50         }51         printf("%lld\n",m/max1);52     }53     return 0;54 }
View Code

 

hdu 5108 Alexandra and Prime Numbers