1059 Prime Factors （欧拉筛）

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 #include<bits/stdc++.h> using namespace std; int prime[1000000]; bool p[1000000] = { false }; int pnum = 0; void eulersieve(int n) { for (int i = 2; i <= n; i++) { if (p[i] == false)prime[pnum++] = i; for (int j = 0; j < pnum; j++) { if (prime[j] * i > n)break; p[prime[j] * i] = true; if (i%prime[j] == 0)break; } } } int main() { int n; cin >> n; if (n == 1) { cout << "1=1"; //数字为1的时候 return 0; } int l =n; int m = (int)sqrt(n*1.0); eulersieve(m); cout << n << "="; int k = 0; /*for (int j = 0; j < pnum; j++) cout << prime[j] << " ";*/ bool num = false; //如果这个数本身是质数，则输出 n = n while (n > 1 && k < pnum) { int pr = prime[k++]; int c = 0; while (n%pr == 0) { c++; n /= pr; num = true; } if (c > 1 && n > 1)printf("%d^%d*", pr, c); else if (c > 1 && n == 1)printf("%d^%d", pr, c); else if (c == 1 && n>1)printf("%d*", pr); else if (c == 1 && n == 1)printf("%d", pr); } if (!num)cout << l; return 0; }