分解质因数
质数判定
直接判定
质数一定和6的倍数相邻（除了2和3），即$prime=6i\pm1$，除以6必定余1或5，可以利用这个必要条件来减少循环次数：
bool IsPrime(long long x)
{
if (x == 1)
return false;
if (x == 2 || x == 3)
return true;
if (x % 6 != 1 && x % 6 != 5)
return false;
// 下面的x都是 6i+1 或 6i-1
for (int i = 6; i <= sqrt(x); i += 6) // 以6为步长
if (x % (i - 1) == 0 || x % (i + 1) == 0)
return false;
return true;
}
上面第12行只需要判断是否为$6i\pm1$的倍数，因为任意$6i\pm1$的数不可能是2或3的倍数，也就不可能是$6i+2=2(3i+1)$，$6i+3=3(2i+1)$，$6i+4=2(3i+2)$的倍数
上面第12行只需要判断是否为$6i\pm1$的倍数，因为任意$6i\pm1$的数不可能是2或3的倍数，也就不可能是$6i+2=2(3i+1)$，$6i+3=3(2i+1)$，$6i+4=2(3i+2)$的倍数质数表
预先计算出一个数组，值为0或1，表示当前下标是否为质数；然后就可以通过下标访问，快速判断是否为质数
只需几秒钟，就能列出16位十进制数$x$的所有可能质因数（小于$\sqrt x$的所有质数）：
vector<long long> GeneratePrimes(long long x)
{
vector<long long> primes(sqrt(x), 1);
primes[0] = 0;
primes[1] = 0;
for (int i = 2; i < primes.size(); i++)
{
if (primes[i] == 0) continue;
for (int j = 2 * i; j < primes.size(); j += i)
{
primes[j] = 0;
}
}
return primes;
}
算法描述：从i=2开始遍历，将i的倍数全部设为0
分解质因数
可以在有效时间内解出16位十进制合数的所有质因数：
typedef long long Base;
typedef int Exponent;
typedef pair<Base, Exponent> Factor;
vector<Factor> factors;
void PrimeFactorization(long long x)
{
if (x == 1)
{
factors.push_back(make_pair(1, 1));
return;
}
long long i = 2;
int power = 0;
while (i <= x)
{
// 最后一个质因数
if (IsPrime(x))
{
factors.push_back(Factor(x, 1));
break;
}
while (x % i == 0)
{
power += 1;
x /= i;
}
if (power != 0)
factors.push_back(Factor(i, power));
i++;
power = 0;
}
return;
}
轮子
Linux命令行工具factor：
factor 2021041820210418
2021041820210418: 2 3 3 3 17 131 2857 5882353