题目如下：
Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1^k1* p2^k2*…*pm^km.
Input Specification:
Each input file contains one test case which gives a positive integer N in the range of long int.
Output Specification:
Factor N in the format N = p1^k1* p2^k2*…*pm^km, where pi’s are prime factors of N in increasing order, and the exponent kiis the number of pi– hence when there is only one pi, kiis 1 and must NOT be printed out.
Sample Input:97532468Sample Output:97532468=2^2*11*17*101*1291
题目的关键是设计出求下一个素数的函数，注意第一个素数是2。
定义当前素数prime，，当前系数exp，初值prime=2，exp=0，如果输入的值N能整除prime，则把exp++，并且N=N/prime，如果N=1，说明当前系数处理完毕，并且整个数也分解完毕，记录当前prime和exp；如果N不能整除prime，则判断exp是否为0，不为0说明对于这个prime被分解过exp次，也应该记录prime和exp然后把exp置0，然后找到下一个prime继续处理。
最后输出所有记录的值即可，用结构体和vector结合可以方便记录prime和exp。
注意输入的值为1时，应该特殊处理。
#include <iostream>#include <vector>#include <stdio.h>using namespace std;typedef unsigned long ulong;struct Node{ulong p;ulong k;Node(int _p, int _k) : p(_p), k(_k) {}};ulong nextPrime(ulong now){if(now <= 1) return 2;bool isPrime;while(1){now++;isPrime = true;for(ulong factor = 2; factor < now; factor++){if(now % 2 == 0) { isPrime = false; break; }}if(isPrime) return now;}}int main(){ulong prime = 2;vector<Node> nodes;ulong num;cin >> num;ulong exp = 0;ulong originNum = num;if(num == 1){cout << "1=1" << endl;return 0;}while(num != 1){if(num % prime == 0){num /= prime;exp++;if(num == 1) nodes.push_back(Node(prime,exp));}else{if(exp != 0){nodes.push_back(Node(prime,exp));exp = 0;}prime = nextPrime(prime);}}ulong p,k;printf("%ld=",originNum);for(int i = 0; i < nodes.size(); i++){p = nodes[i].p;k = nodes[i].k;if(k == 1) printf("%ld",p);else printf("%ld^%ld",p,k);if(i!=nodes.size() – 1) printf("*");}cout << endl;return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
获得幸福的二法门是珍惜你所拥有的、遗忘你所没有的
