关于算法-数据结构:PAT甲级1059-Prime-Factors

题目粗心：

给出一个 int 范畴的整数，依照从小到大的程序输入其合成为质因数的乘法算式。

算法思路：

此题考查的是质因子合成的内容，对于每一个质因子咱们应用构造体 Factor 进行存储，其中保留了因子和呈现的次数。接下来就是获取数字 N 的每一个质因子.

获取办法如下：

首先应用 prime_table 保留 $10^5$ 以内的所有素数，而后遍历每一个在 2 和根号 N 之间的素数 prime_table[i]，只有N%prime_table[i]==0，阐明prime_table[i] 为 N 的一个质因子, 而后只有 prime_table[i] 还是 N 的因子，就讲对于的次数 count 加一，同时 N 除以 prime_table[i]，当prime_table[i] 不在是 N 的因子的时候，让不同因子的数目 index_factor 加一即可。同时因为对于一个数 N，最多只有一个大于根号 N 的因子，也就是说，在 2 到根号 N 之间的所有因子都曾经处理完毕后,N 仍然不为 1，阐明还有一个大于根号 N 的因子，此时须要记录该因子 (其实就是以后的 N) 和次数(1)。

留神点：

1、对于 N 等于 1 的时候没法合成，须要特判输入，测试点 3 考查。2、因为从 2 开始的素数到第 11 个素数的时候，所有素数的累乘就超过了 int 的返回，所以 factor 数组开到 10 就行了。

提交后果：

AC 代码：

#include <cstdio>
#include <cmath>

using namespace std;

struct Factor{int prime{};// 因子
    int count{};// 个数}factor[10];
int index_factor = 0;

int prime_table[100000];// 素数表
int num = 0;

bool isPrime(int N){if(N<4){return N>1;}
    if(N%6!=1&&N%6!=5) return false;
    for (int i = 5; i < sqrt(N*1.0); i+=6) {if(N%i==0||N%(i+2)==0){return false;}
    }
    return true;
}

// 获取素数表
void init(){for (int i = 2; i < 100000; ++i) {if(isPrime(i)){prime_table[num++] = i;
        }
    }
}

int main(){init();
    int N;
    scanf("%d",&N);
    if(N==1){printf("1=1");// 特判 1，测试点 3 考查
        return 0;
    }
    printf("%d=",N);
    int sqrt_N = (int)sqrt(N*1.0);
    // 遍历每一个素数
    for (int i = 0; i < num&&prime_table[i]<=sqrt_N; ++i) {if (N%prime_table[i]==0){factor[index_factor].prime = prime_table[i];
            while (N%prime_table[i]==0){++factor[index_factor].count;
                N /= prime_table[i];
            }
            ++index_factor;
        }
    }
    // 还存在一个大于根号 N 的因子
    if(N!=1){factor[index_factor].prime = N;
        ++factor[index_factor++].count;
    }
    for (int j = 0; j < index_factor; ++j) {printf("%d",factor[j].prime);
        if(factor[j].count>1){printf("^%d",factor[j].count);
        }
        if(j<index_factor-1) printf("*");
    }
    return 0;
}