质因数分解式

质因数分解式

标签：问题分析

---

知识点

质因数

概念：如果一个质数是某个正整数的因数，那么就说这个质数是这个正整数的质因数。

说明：1没有质因数。

例如：5的质因数为5；6的质因数为2和3；12的质因数为2和3

质因数分解式

概念：一个正整数可以写成由若干个质因数相乘的形式。

性质：任何正整数有且仅有一个质因数分解式。

说明：不考虑正整数1的特殊情况。

例如：5=5；6=2*3；12=2*2*3

---

求质因数分解式的方法

短除法

算法：

1.i=2；

2.如果num%i==0，i作为一个因数，且是质因数，num/=i；反之，i++；

3.重复步骤2。

程序实现：

#include <stdio.h>
int main()
{
    long long int num;
    long long int i=2;
    int cnt=0;
    scanf("%lld",&num);
    printf("%lld=",num);
    while(num>1)
    {
        if(num%i==0)
        {
            num=num/i;
            cnt?printf("*%d",i):printf("%d",i);
            cnt++;
        }
        else i++;
    }
    printf("\n");
    return 0;
 }