PAT甲级1059 Prime Factors (25)（素数筛+求一个数的质因子）

迈不过友情╰ 2021-12-03 11:04 260阅读 0赞

### Prime Factors  ###

### **题目描述** ###

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，则不输出。

注意：

注意n=1的情况特判

注意浮点错误

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 }

转载于:https://www.cnblogs.com/1013star/p/11191635.html