首页 > 代码库 > hdu-5108-Alexandra and Prime Numbers（求最大质因数） （BestCoder Round #19）
hdu-5108-Alexandra and Prime Numbers（求最大质因数） （BestCoder Round #19）
Alexandra and Prime Numbers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
Alexandra has a little brother. He is new to programming. One day he is solving the following problem: Given an positive integer N, judge whether N is prime.
The problem above is quite easy, so Alexandra gave him a new task: Given a positive integer N, find the minimal positive integer M, such that N/M is prime. If such M doesn‘t exist, output 0.
Help him!
The problem above is quite easy, so Alexandra gave him a new task: Given a positive integer N, find the minimal positive integer M, such that N/M is prime. If such M doesn‘t exist, output 0.
Help him!
Input
There are multiple test cases (no more than 1,000). Each case contains only one positive integer N.
$N \leq 1,000,000,000$.
Number of cases with $N > 1,000,000$ is no more than 100.
$N \leq 1,000,000,000$.
Number of cases with $N > 1,000,000$ is no more than 100.
Output
For each case, output the requested M, or output 0 if no solution exists.
Sample Input
3456
Sample Output
1
2
1
2
质因子：在数论里是指能整除给定正整数的质数。
质因数分解： 将一个正整数表示成质因数乘积的过程和得到的表示结果叫做质因数分解。
这个题就可以把n分解，分解成n的质因数的乘积。取最大的一个即可。
这里需要注意的是代码中i的范围，i<sqrt(n)就可以。因为一个数分解出来的质因数项肯定不会有超过两个大于√n的质因数存在=大于√n的质因数至多有1个。
#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>#include<math.h>using namespace std;int main(){ int n, i; while(~scanf("%d", &n)) { if(n==1)//1没有质因子，特殊处理。 { printf("0\n"); continue; } int maxx=1, t = n; for(i=2; i<=(int)sqrt(n*1.0); i++)//需要加‘=’,比如n=4; { while(t%i==0)//因为质因数中有重复，比如336->24 x 3 x 7; { t/=i; maxx = i; } } maxx = max(maxx, t);//当t（！=1）本身为素数时，最大质因子是本身。 printf("%d\n", n/maxx); } return 0;}
最后加上素因数表：http://zh.wikipedia.org/wiki/%E7%B4%A0%E5%9B%A0%E5%AD%90%E8%A1%A8
hdu-5108-Alexandra and Prime Numbers（求最大质因数） （BestCoder Round #19）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。