育才学习网1. 分解质因数的C语言怎么写
#include <stdio.h>
#include <math.h>
void analyze(int n)
{
int a[20];
int count = 0;
int i;
int number = n;
while(1)
{
for(i = 2; i < (int)sqrt(n); i++)
{
if(number % i == 0)
{
a[count] = i;
count++;
number = number / i;
break;
}
}
if(number == 1)
{
break;
}
}
printf("%d = ", n);
for(i = 0; i < count; i++)
{
printf("%d * ", a[i]);
}
printf("\b\b");
}
void main()
{
int number;
printf("please input a number: ");
scanf("%d", &number);
analyze(number);
}
2. 分解质因数的方法
1、相乘法
写成几个质数相乘的形式（这些不重复的质数即为质因数），实际运算时可采用逐步分解的方式。
如：36=2*2*3*3 运算时可逐步分解写成36=4*9=2*2*3*3或3*12=3*2*2*3
2、短除法
从最小的质数除起，一直除到结果为质数为止。分解质因数的算式的叫短除法。
扩展资料：
定理
不存在最大质数的证明：（使用反证法）
假设存在最大的质数为N，则所有的质数序列为：N1,N2,N3……N
设M=(N1*N2*N3*N4*……N)+1,
可以证明M不能被任何质数整除，得出M也是一个质数。
而M>N，与假设矛盾，故可证明不存在最大的质数。
最大公约数的求法：
1、用分解质因数的方法，把公有的质因数相乘。
2、用短除法的形式求两个数的最大公约数。
3、特殊情况：如果两个数互质，它们的最大公约数是1。
如果两个数中较小的数是较大的数的约数，那么较小的数就是这两个数的最大公约数。
参考资料来源：百度百科——分解质因数