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.
Each input file contains one test case which gives a positive integer N in the range of long int.
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.
97532468
97532468=2^2*11*17*101*1291
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 typedef long long ll;
7 const long long maxn=1e6+10;
8 ll prime[maxn];
9 ll num[maxn];
10 int k=0;
11 void get_prime()
12 {
13 for(ll i=2;i<maxn;i++)
14 {
15 if(prime[i]==0)
16 {
17 num[k++]=i;
18 for(ll j=i+i;j<maxn;j+=i)
19 prime[j]=1;
20 }
21 }
22 }
23 ll n;
24 int main()
25 {
26 get_prime();
27 cin>>n;
28 if(n==1)
29 cout<<"1=1"<<endl;
30 else
31 {
32 ll tmp=n;
33 printf("%lld=",tmp);
34 //for循环写成num[i]<=n会浮点错误
35 for(ll i=0;i*i<=tmp;i++)
36 {
37 int cnt=0;
38 if(n%num[i])
39 continue;
40 while(n%num[i]==0)
41 {
42 n/=num[i];
43 cnt++;
44 }
45 if(cnt!=1)
46 printf("%lld^%d",num[i],cnt);
47 else
48 printf("%lld",num[i]);
49 if(n!=1)
50 printf("*");
51 }
52 if(n!=1)
53 printf("%lld",n);
54 }
55 }
PAT甲级1059 Prime Factors (25)（素数筛+求一个数的质因子）
原文：https://www.cnblogs.com/1013star/p/11191635.html