1059 Prime Factors （25 分）
Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p?1???k?1????×p?2???k?2????×?×p?m???k?m????.
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 = p?1??^k?1??*p?2??^k?2??*…*p?m??^k?m??, where p?i??'s are prime factors of N in increasing order, and the exponent k?i?? is the number of p?i?? -- hence when there is only one p?i??, k?i?? is 1 and must NOT be printed out.
Sample Input:
97532468
Sample Output:
97532468=2^2*11*17*101*1291
- 题解：先建立一个一万以内的素数表，然后再从第一个素数开始往后判断是否为n的因子，并统计这个素因子出现的次数。注意特判 n == 1的情况。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <vector> #define ll long long using namespace std; map<ll, int> mp; vector<ll> v; void Prime(ll n){mp.clear();for(ll i = 2; i <= 10000; i++){if(mp[i] == 1) continue;v.push_back(i);//i是素数for(ll j = i; j <= 10000/i; j++){mp[i*j] = 1;}} } int main() {ll n, cnt = 0;scanf("%lld", &n);if(n == 1){//特例printf("1=1\n");return 0;}Prime(n);printf("%lld=", n);int flag = 0;//flag用于标记是否是第一个素因子，用于输出格式的控制for(int i = 0; i < v.size(); i++){cnt = 0;if(n % v[i] == 0){if(flag) printf("*%lld", v[i]);else printf("%lld", v[i]);flag = 1;while(n % v[i] == 0){n /= v[i];cnt++;}if(cnt > 1){//该素因子个数大于1则输出指数printf("^%lld", cnt);}}}printf("\n");return 0; }