[数论]分解质因数
Description
每一个大于等于2的自然数,均可写成一个或多个质数的乘积,例如:
2=2 20=2*2*5
这种将一个整数分割成若干个质数之积的操作叫做分解质因数。现在,给你一个整数N,请你编写一个程序,对其分解质因数。
Input Format
输入为一行,正整数N,保证1<N<21474836471<N<2147483647。
Output Format
输出N的质因数分解形式,格式为 N=P1(E1)P2(E2)P3(E3).... 其中,P1、P2、P3、……为组成N的各个质因子,
满足P1 < P2 < P3 < ...;E1、E2、E3、……分别为P1、P2、P3、……在N中的指数。
例如:
20=2*2*5
应该输出成:
20=2(2)5(1)
Hint
N的大于sqrt(N)的质因子至多有一个。(sqrt(n)指N的开方取整)
Sample Input
20
Sample Output
<code>20=2(2)5(1)</code><br /><br />思路:分解质因数模板的应用。下面给出模板:(模拟短除法———从最小的质数2除起,一直除到结果为质数为止)
#include<cstdio> int main(){ int n; scanf("%d",&n); printf("%d=",n); for(int i=;i*i<=n;i++){//n在变小,时间复杂度小于根号n while(n%i==){ n/=i; printf("%d",i); if(n!=) printf("*"); } } if(n!=) printf("%d",n); printf("\n"); return ; }
AC代码:
#include <iostream> #include<cstdio> using namespace std; int main() { int n; scanf("%d",&n); printf("%d=",n); for(int i=;i*i<=n;i++){ if(n%i==){ int tmp=; while(n%i==){ n/=i; tmp++; } printf("%d(%d)",i,tmp); } } if(n!=) printf("%d(1)",n); printf("\n"); return ; }
<br /><br /><br /><br /><br />