分解因数(PAT)
1.题目描述
所谓因子分解，就是把给定的正整数a，分解成若干个素数的乘积，即 a = a1 × a2 × a3 × … × an,并且 1 < a1 ≤ a2 ≤ a3 ≤ … ≤ an。其中a1、a2、…、an均为素数。
先给出一个整数a，请输出分解后的因子。
2.输入描述:
输入包含多组数据，每组数据包含一个正整数a（2≤a≤1000000）。
3.输出描述:
对应每组数据，以“a = a1 * a2 * a3…”的形式输出因式分解后的结果。
4.输入例子:
10
18
5.输出例子:
10 = 2 * 5
18 = 2 * 3 * 3
6.解题思路：
由题意，需要我们求出可以整除n的数，
我们可以从2开始循环到根号n，判断是否能整除n <mark>（大于根号n的数不可能整除，减小循环次数）</mark>
每判断一次按要求输出可以整除的数并用该数将n整除，直到i==n结束循环（因为被整除后的n可能会小于根号n，而i递增循环不能大于被整除后的n，故以此为结束条件）
最后输出不能再被整除的n
7.源代码：
#include<stdio.h>
#include<math.h>
int main()
{
int i,n;
while(scanf("%d",&n)!=-1)
{
printf("%d = ",n);
for(i=2;i<=sqrt(n);i++)
while(n!=i)
{
if(n%i==0)
{
printf("%d * ",i);
n/=i;
}
else
break;
}
printf("%d\n",n);
}
return 0;
}
