PAT A1059

标签（空格分隔）： PAT

---

解题思路 ：先打印出素数表。利用结构体数组来存贮质因子的值和个数

strcut factor{

    int x;    //值

    int cnt;  //个数

}fac[20];

• 如果i是x的质因子，就令fac[index].x = i(index是某个下标), fac[index].cnt = 0,然后 n = n / i。若又遇到i是x的质因子，则cnt++。
• 进行完上述操作后，n != 1,则说明n还有一个大于sqrt（n）的质因子（可能就是sqrt（n）），我们需要加入这个值到fac[index]中，在将fac[index].cnt设为1；

#include <cstdio>

#include <math.h>

const int maxn = 100010;

bool is_prime(int n) {

    if(n == 1) return false;

    int sqr = (int)sqrt(1.0 * n);

    for(int i = 2; i <= sqr; i++) {

        if(n % i == 0) return false;

    }

    return true;

}

int prime[maxn], pNum;

void Find_Prime() {

    for(int i = 1; i < maxn; i++) {

        if(is_prime(i) == true){

        prime[pNum++] = i;

        }

    }

}

struct factor {

    int x, cnt;

}fac[10];

int main() {

    Find_Prime();

    int n, num = 0;

    scanf("%d", &n);

    if (n == 1) printf("1=1");

    else {

        printf("%d=", n);

        int sqr = (int)sqrt(1.0 * n);

        for(int i = 0; i < pNum; i++) {

            if(n % prime[i] == 0) {

                fac[num].x = prime[i];

                fac[num].cnt = 0;

                while(n % prime[i] == 0) {

                    fac[num].cnt++;

                    n /= prime[i];

                }

                num++;

            }

            if(n == 1) break;

        }

        if(n != 1) {

            fac[num].x = n;

            fac[num].cnt = 1;

        }

        for(int i = 0; i < num; i++) {

            if(i > 0) printf("*");

            printf("%d", fac[i].x);

            if(fac[i].cnt > 1) {

                printf("^%d", fac[i].cnt);

            }

        }

    }

    return 0;

}

启示 ：边写边测试，我写过用埃氏筛法得到素数表的时候，发现最后的结果是错的，

结果我验证发现我的素数表是错误的，但埃氏筛法肯定是没有写错了，最后为什么素数表是错的，原因我也不知道，但是这可以为我后来做题提供经验，写出一个模块就验证一下功能。