给定某个正整数N,求其素因子分解结果,即给出其因式分解表达式 N = p1^k1 * p2^k2 *…*pm ^km。
输入格式说明:
输入long int范围内的正整数N。
输出格式说明:
按给定格式输出N的素因式分解表达式,即 N = p1^k1 * p2^k2 *…*pm ^km,其中pi为素因子并要求由小到大输出,指数ki为pi的个数;当ki==1即因子pi只有一个时不输出ki。
样例输入与输出:
序号 | 输入 | 输出 |
1 |
1024
|
1024=2^10
|
2 |
1323
|
1323=3^3*7^2
|
3 |
97532468
|
97532468=2^2*11*17*101*1291
|
4 |
1
|
1=1
|
5 |
3
|
3=3
|
//关于素因子分解,这是数论中(密码学运用)最基本也是最重要的问题之一,由于本题的数据并不是很大,故可运用下面的简单的方法,但是效率却不是很高(PAT上足以AC),若有兴趣可参见TAOCP (<<计算机程序设计与艺术>>,计算机界"易筋经"级别书籍)卷二中的半数值算法中有关的数学推导与证明。
#include <iostream> #include <cmath> using namespace std; int main() { long int N; long int i; long int m; int k=0; bool flag = false; bool isPrime = true; cin>>N; m = (long int)sqrt(N+0.5); cout<<N<<"="; for (i=2;i<=m;i++) { k=0; while(N%i==0) { k++; N/=i; isPrime = false; } if (k) { if (flag) cout<<"*"; else flag = true; if (k==1) cout<<i; else cout<<i<<"^"<<k; } } if (isPrime) cout<<N; cout<<endl; //system("pause"); return 0; }