PTA A_1059 Prime Factors

798236606

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805415005503488

解：

1. #include<stdio.h>
   
2. #include<math.h>
   
3. 
   
4. typedef struct{
   
5.     int x, cnt;
   
6. }factor;
   
7. 
   
8. int prime[10010];      
   
9. int is_not_p[1000010] = {0};     
   
10. factor fac[10];
    
11. 
    
12. int find_prime(int n)   
    
13. {
    
14.     int i, j, p_num = 0;
    
15.    
    
16.     for (i = 2; i <= n; i++)
    
17.     {
    
18.         if (!is_not_p[i])
    
19.             prime[p_num++] = i;
    
20.                
    
21.         for (j = 0; j < p_num && i * prime[j] <= n; j++)      
    
22.         {
    
23.             is_not_p[i * prime[j]] = 1;
    
24.             
    
25.             if (i % prime[j] == 0)        
    
26.                 break;
    
27.         }
    
28.     }
    
29.    
    
30.     return p_num;
    
31. }
    
32. 
    
33. int main(void)
    
34. {
    
35.     int i, n, p_num, f_num = 0;
    
36.    
    
37.     scanf("%d", &n);
    
38.     printf("%d=", n);
    
39.    
    
40.     if (n == 1)
    
41.         putchar('1');
    
42. 
    
43.     p_num = find_prime((int)sqrt((double)n));
    
44.    
    
45.     for (i = 0; i < p_num; i++)
    
46.     {
    
47.         if (n % prime[i] == 0)
    
48.         {
    
49.             fac[f_num].x = prime[i];
    
50.             fac[f_num].cnt = 1;
    
51.             n /= prime[i];
    
52.             
    
53.             while (n % prime[i] == 0)
    
54.             {
    
55.                 fac[f_num].cnt++;
    
56.                 n /= prime[i];
    
57.             }
    
58.             
    
59.             f_num++;
    
60.         }
    
61.     }
    
62.    
    
63.     if (n != 1)
    
64.     {
    
65.         fac[f_num].x = n;
    
66.         fac[f_num++].cnt = 1;        
    
67.     }
    
68.    
    
69.     for (i = 0; i < f_num; i++)
    
70.     {
    
71.         printf("%d", fac[i].x);
    
72.         
    
73.         if (fac[i].cnt > 1)
    
74.             printf("^%d", fac[i].cnt);
    
75.             
    
76.         if (i < f_num - 1)
    
77.             putchar('*');
    
78.     }
    
79.    
    
80.     return 0;
    
81. }
    

复制代码