38:质因数分解
总时间限制: 1000ms 内存限制: 65536kB
描述
已知正整数 n 是两个不同的质数的乘积，
试求出较大的那个质数。
输入
输入只有一行，包含一个正整数 n。
对于60%的数据，6 ≤ n ≤ 1000。
对于100%的数据，6 ≤ n ≤ 2*10^9。
输出
输出只有一行，包含一个正整数 p，即较大的那个质数。
样例输入
21
样例输出
7
来源 NOIP2012复赛 普及组 第一题
分析：
这个题目要注意“正整数 n 是两个不同的质数的乘积”这个条件。假定n是由p和q两个质数相乘得到的，那么n只有1，n，p，q四个因数。所以，对n枚举除了1和n之外的因数，只要发现即可解决问题。
1 #include <stdio.h> 2 int main(int argc, char *argv[]) 3 { 4 long n,i,t; 5 scanf("%ld",&n); 6 t=n/2; 7 for(i=2;i<=t;i++) 8 { 9 if(n%i==0) 10 { 11 printf("%ld\n",n/i); 12 break; 13 } 14 } 15 return 0; 16 }
