【c语言】--分解质因数【完整版详细】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【c语言】--分解质因数【完整版详细】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、质因数是什么？

首先，我们所说的质数就是素数，两种叫法都可以！
如果一个数的因数是质数,那么这个因数就是他的质因数。
比如：
5的因数：1、5 因数5就是5的质因数。
28的因数：4、7 因数7就是28的质因数。

2、什么是分解质因数？

把一个合数用质数相乘的形式表示出来，叫作分解质因数。他强调的是分解的过程
1、合数可以分解质因数，质数不能分解质因数，因为质数只能等于1*本身这种形式，而1不是质数。
2、分解质因数不是一个具体的数，而是把一个合数分解为成几个质数相乘的过程

3、怎么分解质因数？

不妨我们先引入一道编程题

题目：输入你要分解质因数的数的范围，输出每个数分解质因数的因数输入样例： 3 10 输出样例： 3=3 4=2 * 2 5=5 6=2 * 3 7=7 8=2 * 2 * 2 9=3 * 3 10=2 * 5

分解质因数的过程

1、我们先以8为例

我们先以最小的质数2开始试
8/2=4此时是不是还能除以2，那么再4/2=2 此时最后2为质数了，这就成为了终止条件，所以8 = 2 * 2 * 2
2、我们再以9为例

还是从2开始试
9/2 无法整除，那么2加1=3，判断3为素数，所以有可能是9的质因数，9/3=3，此时3为质数了，这成为了终止条件所以9 = 3 * 3
2、我们再以10为例

还是从2开始试
10/2=5，5直接为质数，直接达到终止条件，所以10 = 2 * 5
总结：
从2开始作为因子，能整除就一直除，直到最后的结果为质数再终止，那么结果就等于{你要分解的数=之前被除的因子*最后的终止条件（质数）
如果2不能整除了，就往上+1，然后还要判断被+1的数是否为质数，只有他是质数才有作为质因子的必要！然后再让你要分解的数除以这个因子，看是否能整除，不能整除就+1

最后代码如下，详细讲解均在代码块里面！按理来说，质数的分解不算分解质因数过程，但下列代码包括质数的分解，不要产生误解！

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
int isprime(int n)
{
	int flag = 1;
	int i = 0;
	for (i = 2; i <= sqrt(n); i++)//别忘了sqrt要引头文件math.h
	{
		if (n % i == 0)
		{
			flag = 0;
			break;
		}
	}
	return flag;
		
}
int main()
{
	//1、用min和max变量确定你要求质因数的数的范围
	//比如输入3 10 就会帮助你求3-10这每个数所能分解的质因数
	int min = 0;
	int max = 0;
	int i = 0;
	int j = 0;
	printf("请输入你想获得质因数的数的范围\n");
	scanf("%d %d", &min, &max);
	//2、写一个判断是否为素数的函数isprime()
	//如果是素数直接写出该素数=该素数
	//如果判断为合数，就要用合数分解质因数的方法。
	for (i = min; i <= max; i++)
	{
		if (isprime(i))
		{//为真则为质数，直接输出
			printf("%d=%d\n", i, i);
		}
		else
		{
	    //既然进了else就说明是合数了
			int tmp = i;//tmp为临时保存i的值，防止i在后面的操作中被改变
			printf("%d=", tmp);
			for (j = 2; j < tmp; j++)
			{//这里j从二开始，因为我此时分解合数，最小的质数是2，所以从2开始
			 //还应注意的是必须是j<tmp，如果多一个=，那还分解什么合数，直接等于本身*1了
				if (isprime(j))
				{//判断是否为质数，因为分解质因数的前提是因子必须为质数的前提下
					while (tmp % j == 0)
					{
						printf("%d*", j);
						tmp /= j;
						if (isprime(tmp))
						{//一直除以质因子，直到有一次除出来结果是质数，说明分解质因数完毕
							printf("%d", tmp);
							break;
						}
					}

				}
			}
			printf("\n");
		}
	}
	return 0;

}