蓝桥杯基础练习VIP-分解质因数 （C语言代码）（自己带个数进去就知道了）

解题思路:

先按照题目的思路先判断是不是素数，是素数就是本身，不是就开始分解

例如3是素数，那么输出3=3：4不是，分解输出4=2*2；

举个简单的例子进行分解 如 64=2*2*2*2*2；

for(i = 2; i <= n; i++)一开始从2开始，那么64%2 == 0，那么2是它的因子，

那么(重点，int t,用 t 保存 64，因为它一直不会变)来了，剩下的因子的乘积就等于 -> t/2=32，我们就从 32 里面取剩下的因子，i 最多取到 32，

那么原来的for循环的 i 的最终值要变成 32，题目又要求是因子必须是质数，那么 i 的初始值 从 i = 2开始。

依此类推，一步一步得分解！ 解的过程中，用数组保存质因子。

注意事项:

        代码用C耗时40ms，C++的200多。。。

参考代码:

#include<stdio.h>
#include<math.h>
int prime(int n)  //验证素数 
{
	int i, x, t;
	t =	(int)(sqrt(n));
	for(i = 2; i <= t; i++)
		if(n%i == 0) return 1;
	return 0;
}
void primetwo(int n)  //分解质因数 
{
	int i, a[100], k = 0, t, sum = 1;
	t = n;
	for(i = 2 ; i <= n ; i++)
	{
		if(n % i == 0)
		{
			a[k] = i;
			sum = sum * a[k];
			n = t / sum;			
			i = 1;	k++;					
		}	
	}
	printf("%d=",t);
	for(i = 0 ; i < k ; i++)
	{
		printf("%d",a[i]);		
		if(i < k - 1) printf("*"); //最后一个没有 * 号 
	}	
	printf("\n");
}
int main()
{		
	int a, b, i;
	scanf("%d%d",&a,&b);
	for(i = a; i <= b; i++)
	{
		if(prime(i))  //不是素数 
		{		
			primetwo(i);
		}
		else
		{
			printf("%d=%d\n",i,i);			
		}
	}		
	return 0;	
}