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 ki is the number of pi -- hence when there is only one pi, ki is 1 and must NOT be printed out.
Sample Input:97532468Sample Output:
97532468=2^2*11*17*101*1291
#include <iostream>#include <vector>using namespace std;vector<long int> factor;vector<long int> exponent;bool isPrime(long int a) {if (a == 2 || a == 3)return true;for (long int i = 2; i*i < a; i++)if (a%i == 0)return false;return true;}int main(void) {long int n;cin >> n;cout << n << "=";if (n < 2) {cout << n;return 0;}long int i = 2;while (true){if (!isPrime(i)) {i++;continue;}if (n%i == 0) {int expCnt = 0;factor.push_back(i);while (true){if (n%i == 0) {n = n / i;expCnt++;}else {exponent.push_back(expCnt);break;}}}i++;if (n == 1) {break;}}for (int i = 0; i < exponent.size(); i++) {if (exponent[i] == 1)cout << factor[i];elsecout << factor[i] << "^" << exponent[i];if (i != exponent.size() - 1)cout << "*";}return 0;}
原文：http://www.cnblogs.com/zzandliz/p/5023191.html