1059 Prime Factors

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

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 100010;

long n;
bool isPrime[maxn]; // 是否是素数 
vector<long> prime; // 素数的数组 

void init() {
	fill(isPrime,isPrime+maxn,true);
	for(long i=2; i<maxn; i++) {
		if(isPrime[i]) {
			prime.push_back(i);
			for(long j=i+i; j<maxn; j+=i) {
				isPrime[j] = false;
			}
		}
	}
	isPrime[1] = false;
}

int main(){
	init();

	cin >> n;
	cout << n << "=";
	
	if(n == 1) {
		cout << 1;
		return 0;
	}
	
	for(long i=0,j=0; n>1 ; i++) {
		long coun = 0;
		while(n%prime[i]==0 && n>1) {
			n /= prime[i];
			coun++;
		}
		
		if(coun >= 1) {
			if(j == 1) {
				cout << "*";
			}
			cout << prime[i];
			if(coun > 1) {
				cout << "^" << coun;
			}
			j = 1; 
		}
	}
	return 0;
}