问题
13195的素因数为5、7、13和29。
求600851475143的最大素因数。
* 传送门
分析
显然，这是一个给出任意整数然后因数分解的问题。假设该整数为N，而整数分解问题最直接粗暴的解决方法就是从2到N逐个遍历，当发现这个数是素数时，便尝试一下N是否能被该素数整除，最后一个能整除的素数就是最大素因数，整个过程的关键在于是否能够快速判断一个数是否为素数。判断一个数是否为素数是一个数学大问题，极大的问题，所以这里就不展开了，这里直接使用试除法，从2到\(\sqrt N\)的奇数进行试除（所有素数除了2之外都是奇数），其他判断素数的方法还有很多。
对于任意整数N，若p为N的最大素因数，则：\(N = 2^a \times 3^b \times \dots \times p^n\)。
以13195为例子，素数指数为0的略去：\(13195 = (5 \times 2639) = 5^1 \times (7 \times 377) = 5^1 \times 7^1 \times (13 \times 29) = 5^1 \times 7^1 \times 13^1 \times 29^1\)，29即为最大素因数，每次将一个数分解为带括号的乘法，便是若干次试除的中间过程。
答案
// answer: odd number divide test
const start = Date.now()
function isPrime(n) {
if (n == 2 || n == 3 || n == 5 || n == 7) // small short cut
return true
else if (n < 2)
return false
if ((n % 2) == 0)
return false
const end = Math.sqrt(n)
for (let i = 3; i <= end; i += 2) // 只测试奇数
if ((n % i) == 0)
return false
return true
}
function largestPrimeFactor(n, primeTest) {
var primeFactors = []
function divideTest(p) {
if (primeTest(p)) {
let divisible = false
while ((n % p) == 0) {
n /= p
divisible = true
}
if (divisible)
primeFactors.push(p)
}
}
let i = 2
divideTest(i++)
// n每次被试除后都有变化，如果n自己本身为素数就不用再继续了
for (; n > 2 && !primeTest(n); i += 2) // 只用奇数进行试除
divideTest(i)
if (n > 1) // 如果一个数字是p^x形式的，最终n会等于1，但1不是素数，
primeFactors.push(n)
return primeFactors[primeFactors.length-1]
}
alert(largestPrimeFactor(600851475143, isPrime) + ', ' + (Date.now() - start) + 'ms')
由 bruce 于 2020-06-8 19:47 更新
