程序设计-素因子分解
本文介绍试除法和费马因子分解法来分解正整数的素因子
算术基本定理：每个大于1的正整数都可以被唯一地写成素数的乘积。
乘积的组成为该正整数的素因子。
例：18 = 3 ? 3 ? 2 即18的素因子为3，3，2
试除法
依次使用不超过根号n的素数p除n。如果能够整除，则p为n的素因子。将整除后的数字继续使用素数整除，直到除到1或者除到素数。
例:
42833 = 7 ? 6119
6119 = 29 ? 211
43833 = 7 ? 29 ? 211 // 43833的素因子为7，29，211
36 = 2 ? 18
18 = 2 ? 9
9 = 3 ? 3
3 = 3 ? 1 // 36的素因子为2，2，3，3
程序设计
1⃣️ 求不超过根号n的素数
先使用Math.sqrt取n的平方根squareRoot
// 求整数的整数平方根
let squareRoot = Math.floor(Math.sqrt(n));
求小于squareRoot的素数
// 从小于平方根的数里求素数
for (let i = 2; i <= squareRoot; i ) {
// 是否合数（即非素数的自然数
let isComposite = false;
for (let j = 2; j < i; j ) {
if (i % j == 0) {
isComposite = true;
break;
if (!isComposite) lessThanSquareRootPrimeNum.push(i);
求得不超过根号n的素数表lessThanSquareRootPrimeNum
2⃣️ 尝试除每一个小于平方根n的素数
能够被整除的即为素因子
let finish = false;
while(!finish) {
// 如果能被整除
if ((divisionNum % lessThanSQRTNPrimeTable[divisionPrimePoint]) == 0) {
// 如果能整除 将这个素因子放入结果
nPrimeFactorization.push(lessThanSQRTNPrimeTable[divisionPrimePoint]);
// 除数除此素数
divisionNum /= lessThanSQRTNPrimeTable[divisionPrimePoint];
} else {
// 如果不能整除 尝试下一个素数
divisionPrimePoint = 1;
// 注意 如果除数被除到1 或所有小于根号n的素数都无法除这个数 循环调节结束
if (divisionNum == 1 || divisionPrimePoint >= lessThanSQRTNPrimeTable.length) finish = true
3⃣️ 注意最后的素数
除到最后 没有可以被除的素数了 那这个除数就是素数
if (divisionPrimePoint >= lessThanSQRTNPrimeTable.length && divisionNum != 0) nPrimeFactorization.push(divisionNum)
代码实现
* @method getLessThanSQRTNPrimeTable 求小于平方根n的素数
* @params {number} n 正整数
* @return {Array<number>} lessThanSquareRootPrimeNum 小于平方根n的素数表
**/
let getLessThanSQRTNPrimeTable = (n) => {
// 求整数的整数平方根
let squareRoot = Math.floor(Math.sqrt(n));
// 比整数平方根小的素数
let lessThanSquareRootPrimeNum = [];
// 从小于平方根的数里求素数
for (let i = 2; i <= squareRoot; i ) {
// 是否合数（即非素数的自然数
let isComposite = false;
for (let j = 2; j < i; j ) {
if (i % j == 0) {
isComposite = true;
break;
if (!isComposite) lessThanSquareRootPrimeNum.push(i);
return lessThanSquareRootPrimeNum;
* @method getNPrimeFactorization 获取n的素数分解
* @params { number } 正整数
* @return { Array<number> } 素数分解
**/
let getNPrimeFactorization = (n) => {
if (n < 2) return [];
// 小于根号n的所有质数
let lessThanSQRTNPrimeTable = getLessThanSQRTNPrimeTable(n);
// 待除的素数指针
let divisionPrimePoint = 0;
// 被除数
let divisionNum = n;
// n的所有素数分解
let nPrimeFactorization = []
let finish = false;
while(!finish) {
// 如果能被整除
if ((divisionNum % lessThanSQRTNPrimeTable[divisionPrimePoint]) == 0) {
nPrimeFactorization.push(lessThanSQRTNPrimeTable[divisionPrimePoint]);
divisionNum /= lessThanSQRTNPrimeTable[divisionPrimePoint];
} else {
// 如果不能整除 尝试下一个素数
divisionPrimePoint = 1;
if (divisionNum == 1 || divisionPrimePoint >= lessThanSQRTNPrimeTable.length) finish = true
if (divisionPrimePoint >= lessThanSQRTNPrimeTable.length && divisionNum != 0) nPrimeFactorization.push(divisionNum)
return nPrimeFactorization;
console.log(getNPrimeFactorization(33776925)); // [3,5,5,7,7,7,13,101]
费马因子分解法
费马因子分解法基于引理：
如果n是一个正的奇数，那么n分解为两个正整数的积和表示成两个平方数的差是一一对应的。n = a ? b = s ^ 2 ? t ^ 2 = (s - t) ?(s t) 其中s = (a b) / 2. t = (a - b) / 2
使用费马因子分解法分解，首先向上取整根号n的数m，取m ^ 2 - n = q 如果q为完全平方数，则取q的平方根a, 如果m不是完全平方数 那么取m = m 1，重复前一步。最后n的素因子分解为（m - a）和（m a）即n = (m - a) ? (m a)
例：使用费马因子分解6077.
// 由于根号6077 < 78 所以m为78
78 ^ 2 - 6077 = 7 // 7 不是完全平方数 所以 m 1 = 79
79 ^ 2 - 6077 = 164 // 164 不是完全平方数 所以 m 1 = 80
80 ^ 2 - 6077 = 323 // 323 不是完全平方数 所以 m 1 = 81
81 ^ 2 - 6077 = 484 // 484 为完全平方数 所以 a = 根号484 = 22
得a = 22 m = 81
所以6077 = (81 - 22)(81 22) = 59 ? 103
即6077的素因子为59，103
注意：费马因子分解法仅适用于奇数。
程序设计
1⃣️ 边界判断
由于费马因子分解只适用于奇数 所以如果是偶数 则直接不处理。
2⃣️ 取平方根 1
使用Math.sqrt(n)取平方根并取整 1作为我们基础的求值数
代码实现
* @method getPrimeFactByFermat 获取素因子分解通过费马因子分解法
* @params { number } 整数 只能是奇数
* @return { Array<number> } 素因子
**/
let getPrimeFactByFermat = (n) => {
// 只处理奇数
if (n % 2 == 0) return [];
// 素数无法拆解
if (isPrimeNumber(n)) return [1, n];
// 取整数平方根
let nSQRTRoot = Math.floor(Math.sqrt(n));
let baseNumber = nSQRTRoot 1;
// 另一个素因子
let otherPrime = 0
while (otherPrime == 0) {
let diff = Math.pow(baseNumber, 2) - n;
let sqrtDiff = Math.sqrt(diff)
// 如果差为平方数
if (sqrtDiff % 1 == 0) {
otherPrime = sqrtDiff
} else {
baseNumber = 1
return [baseNumber - otherPrime, baseNumber otherPrime]
console.log(getPrimeFactByFermat(3200399)) // [1601,1999]
