sdut-C语言实验-合数分解

分数 12

全屏浏览

切换布局

作者 马新娟

单位 山东理工大学

合数是指在大于1的整数中，除了1和本身外，还能被其他数整除的数。‌例如，4、6、8、9、10等都是合数。把一个合数分解成若干个质因数乘积的形式(即求质因数的过程)叫做分解质因数。分解质因数(也称分解素因数)只针对合数。比如12的因数有1, 2, 3, 4, 6, 12，质因数为2和3，所以分解后的式子为：12 = 2 × 2 × 3。
在实际应用中，质因数分解常用于数学、密码学等领域。例如，在数学中，质因数分解可以帮助我们理解数的性质；在密码学中，质因数分解是RSA加密算法的基础。
现要求输入一个正整数n，将n分解成质因数乘积的形式。
（题目来源：Teacher Liu,SDUT）

输入格式:

输入一个正整数n（2≤n≤20000）。

输出格式:

输出n分解成质因数乘积的形式。

输入样例1:

36

输出样例1:

36=2^2*3^2

输入样例2:

1885

输出样例1:

1885=5*13*29

#include <stdio.h>
void primeFactorization(int n)
{int i;printf("%d=",n);for(i=2;i<=n;i++){int count=0;while(n%i==0){count++;n/=i;}if(count>0){if(count>1)printf("%d^%d",i,count);elseprintf("%d",i);if(n>1)printf("*");}}
}
int main()
{int n;scanf("%d",&n);primeFactorization(n);return 0;
}