鱼C论坛

 找回密码
 立即注册
查看: 2697|回复: 0

[技术交流] PTA A_1059 Prime Factors

[复制链接]
发表于 2020-1-31 17:01:04 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 798236606 于 2020-1-31 16:58 编辑

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

解:
  1. #include<stdio.h>
  2. #include<math.h>

  3. typedef struct{
  4.     int x, cnt;
  5. }factor;

  6. int prime[10010];      
  7. int is_not_p[1000010] = {0};     
  8. factor fac[10];

  9. int find_prime(int n)   
  10. {
  11.     int i, j, p_num = 0;
  12.    
  13.     for (i = 2; i <= n; i++)
  14.     {
  15.         if (!is_not_p[i])
  16.             prime[p_num++] = i;
  17.                
  18.         for (j = 0; j < p_num && i * prime[j] <= n; j++)      
  19.         {
  20.             is_not_p[i * prime[j]] = 1;
  21.             
  22.             if (i % prime[j] == 0)        
  23.                 break;
  24.         }
  25.     }
  26.    
  27.     return p_num;
  28. }

  29. int main(void)
  30. {
  31.     int i, n, p_num, f_num = 0;
  32.    
  33.     scanf("%d", &n);
  34.     printf("%d=", n);
  35.    
  36.     if (n == 1)
  37.         putchar('1');

  38.     p_num = find_prime((int)sqrt((double)n));
  39.    
  40.     for (i = 0; i < p_num; i++)
  41.     {
  42.         if (n % prime[i] == 0)
  43.         {
  44.             fac[f_num].x = prime[i];
  45.             fac[f_num].cnt = 1;
  46.             n /= prime[i];
  47.             
  48.             while (n % prime[i] == 0)
  49.             {
  50.                 fac[f_num].cnt++;
  51.                 n /= prime[i];
  52.             }
  53.             
  54.             f_num++;
  55.         }
  56.     }
  57.    
  58.     if (n != 1)
  59.     {
  60.         fac[f_num].x = n;
  61.         fac[f_num++].cnt = 1;        
  62.     }
  63.    
  64.     for (i = 0; i < f_num; i++)
  65.     {
  66.         printf("%d", fac[i].x);
  67.         
  68.         if (fac[i].cnt > 1)
  69.             printf("^%d", fac[i].cnt);
  70.             
  71.         if (i < f_num - 1)
  72.             putchar('*');
  73.     }
  74.    
  75.     return 0;
  76. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-7 09:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表