C语言–质因数分解(非常简洁的代码实现)

这是百度上的概念:分解质因数只针对合数。(分解质因数也称分解素因数)求一个数分解质因数,要从最小的质数除起,一直除到结果为质数为止。分解质因数的算式叫短除法,和除法的性质相似,还可以用来求多个数的公因式

正文:
首先,质因数分解是针对非素数的,每一个非素数可以表示成它的部分因子乘积之和(可重复)例如 28 = 2 * 2 * 7

我们来看看怎么操作

例如:90的公因子为2,3,5,9,10,15 ·········

我们要用90从小到大除以它的公因子(注意:一个公因子可以被除多次)

1.我们先用最小的公因子除90: 90/2=45;(这一步分解出因子2)

2.因为45不能被2整除,所以就用下一个公因子3除90: 45/3=15;(这一步分解出因子3)

3.因为15能被当前公因子3整除,那么: 15/3=5;(这一步分解出因子3)

4.继续,因为5不能被3整除,那么:5/5=1(这一步分解除因子5) (这里最后一步的结束条件是得到的数 1 % 9(因数)!= 0)

这里按照我们的顺序把90分成了2 * 3 * 3 * 5

下面再来一个例子:
对28,我们进行分解

  1. 首先 ,28的因子从小到大为 2,4,7,14

  2. 28 / 2 =14;

  3. 14 / 2 = 7;

  4. ​ 7 / 7 = 1; (这里最后一步的结束条件是得到的数 1 % 7(因数)!= 0)

    那么 28 = 2 * 2 * 7;
    由此推出下面的代码

    #include<stdio.h>
    int Isprime(int n)     //函数功能--判断是否为素数
    {
    	for (int i = 2; i < n / 2; i++)
    		if (n % i == 0) return 1;
    	return 0;
    }
    void fun(int n)         //函数功能--质因数分解
    {
    	int i = 0, j;
    	int m = n;
    	for (j = 2;j < m/2; j++)     //从小到大寻找n的因数
    			while(n % j == 0)   //当n%j(因数)== 0时,继续分解
    			{
    				printf("%d*", j);
    				n /= j;
    			}
    }
    int main()
    {
    	int n;
    	int c;
    	scanf("%d", &n);      //输入要分解的数
    	c = Isprime(n);       //判断是否为素数
    	if (c)  fun(n);        //如果不是素数则进行分解
    	else printf("it is a prime\n");   //如果是素数则不用分解
    }
    

    但是我们会发现这段代码运行出来是这样的:

在这里插入图片描述

打印的结果为 2 * 3 * 3 * 5*

尾巴后面多了个乘号

针对这个问题,我们在fun函数的while循环内稍作改动

下面是正解
#include<stdio.h>
int Isprime(int n)
{
	for (int i = 2; i < n / 2; i++)
		if (n % i == 0) return 1;
	return 0;
}
void fun(int n)
{
	int i = 0, j;
	int m = n;
	for (j = 2;j < m/2; j++)
			while(n % j == 0)
			{
				printf("%d", j);
				if (n / j > 2) printf("*");
				n /= j;
			}
}
int main()
{
	int n;
	int c;
	scanf("%d", &n);
	c = Isprime(n);
	if (c)  fun(n);
	else printf("it is a prime\n");
}

这样就可以了。

第一次写这个,有不足的地方请吐槽,谢谢大家!




Logo

为开发者提供学习成长、分享交流、生态实践、资源工具等服务,帮助开发者快速成长。

更多推荐