798236606 发表于 2020-1-31 17:01:04

PTA A_1059 Prime Factors

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

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

解：
#include<stdio.h>
#include<math.h>

typedef struct{
    int x, cnt;
}factor;

int prime;      
int is_not_p = {0};   
factor fac;

int find_prime(int n)   
{
    int i, j, p_num = 0;
   
    for (i = 2; i <= n; i++)
    {
      if (!is_not_p)
            prime = i;
               
      for (j = 0; j < p_num && i * prime <= n; j++)      
      {
            is_not_p] = 1;
            
            if (i % prime == 0)      
                break;
      }
    }
   
    return p_num;
}

int main(void)
{
    int i, n, p_num, f_num = 0;
   
    scanf("%d", &n);
    printf("%d=", n);
   
    if (n == 1)
      putchar('1');

    p_num = find_prime((int)sqrt((double)n));
   
    for (i = 0; i < p_num; i++)
    {
      if (n % prime == 0)
      {
            fac.x = prime;
            fac.cnt = 1;
            n /= prime;
            
            while (n % prime == 0)
            {
                fac.cnt++;
                n /= prime;
            }
            
            f_num++;
      }
    }
   
    if (n != 1)
    {
      fac.x = n;
      fac.cnt = 1;      
    }
   
    for (i = 0; i < f_num; i++)
    {
      printf("%d", fac.x);
      
      if (fac.cnt > 1)
            printf("^%d", fac.cnt);
            
      if (i < f_num - 1)
            putchar('*');
    }
   
    return 0;
}
页: [1]
查看完整版本: PTA A_1059 Prime Factors