分解质因子

• 所谓质因子的分解是指将一个大于1的正整数写成一个或多个质数的乘积
• 例如6=23， 180=2233*5

显然，最后都是关于多个质数的乘积，所以我们可以先打印出素数表准备好。

1.由于每个质因子都可能不止出现过一次，因此我们不仅需要统计质因子数值，还要统计其出现的个数
所以使用结构体比较方便

struct factor {
    int x;  //数值
    int num;  //个数
}fac[10];

因为考虑到 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 就已经超过int的范围
所以，对于一个int范围内的数来说，fac数组我们开到10就已经足够了

对于一个正整数来说，它的质因子要么全部小于sqrt(n),要么只有一个大于sqrt(n)的质因子

• 首先枚举小于sqrt(n)的质数，进行取余判断是否为n的因子。
• 如果是，则在fac数组中添加一个元素,并将其num=0。
• 然后，进行一个小的while循环，截止条件是取余不等于0，让n不断除以该数，num++。
• 在sqrt(n)以内的质数都判断完毕后，如果仍然n!=1，说明还没有被除尽，说明存在一个大于sqrt的数
• 也就是剩下的这个"n",将其添加进去

struct factor{
    int n;
    int num;
}fac[10];
int prime[maxn], pNum;
bool p[maxn] = {false};
//记录质因子的个数
int x;

//埃氏筛法
void Find_Prime() {
    for(int i=2; i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5658693.html