PTA A_1059 Prime Factors

798236606

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

解：

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

typedef struct{
    int x, cnt;
}factor;

int prime[10010];       
int is_not_p[1000010] = {0};     
factor fac[10];

int find_prime(int n)    
{
    int i, j, p_num = 0;
    
    for (i = 2; i <= n; i++)
    {
        if (!is_not_p[i])
            prime[p_num++] = i;
                
        for (j = 0; j < p_num && i * prime[j] <= n; j++)       
        {
            is_not_p[i * prime[j]] = 1;
            
            if (i % prime[j] == 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[i] == 0)
        {
            fac[f_num].x = prime[i];
            fac[f_num].cnt = 1;
            n /= prime[i];
            
            while (n % prime[i] == 0)
            {
                fac[f_num].cnt++;
                n /= prime[i];
            }
            
            f_num++;
        }
    }
    
    if (n != 1)
    {
        fac[f_num].x = n;
        fac[f_num++].cnt = 1;        
    }
    
    for (i = 0; i < f_num; i++)
    {
        printf("%d", fac[i].x);
        
        if (fac[i].cnt > 1)
            printf("^%d", fac[i].cnt);
            
        if (i < f_num - 1)
            putchar('*');
    }
    
    return 0;
}