What is the largest prime factor of the number 600851475143 ?

  • 时间：2020-09-10 12:55:33
  • 分类：网络文摘
  • 阅读：152 次

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

We can start prime number 2 and keep dividing the Number until it can’t, then move to next prime number. Repeat this process until the number becomes 1. Prime number testing can be done in O(Sqrt(N)).

1
2
3
4
5
6
7

function isPrime(n) {
    if (n == 2 || n == 3) return true;
    for (let i = 2; i * i < n; i ++) {
        if (n % i === 0) return false;
    }
    return true;
}
function isPrime(n) {
    if (n == 2 || n == 3) return true;
    for (let i = 2; i * i < n; i ++) {
        if (n % i === 0) return false;
    }
    return true;
}

Running the following Javascript code to find the largest Prime factor:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function largestPrimeFactor(n) {
    let prime = 2;
    while (n > 1) {
        while (n % prime === 0) {
            n /= prime;
        }
        if (n == 1) break;
        do {
           prime ++;
        } while (!isPrime(prime));
    }
    return prime;
}
 
console.log(largestPrimeFactor(600851475143));
function largestPrimeFactor(n) {
    let prime = 2;
    while (n > 1) {
        while (n % prime === 0) {
            n /= prime;
        }
        if (n == 1) break;
        do {
           prime ++;
        } while (!isPrime(prime));
    }
    return prime;
}

console.log(largestPrimeFactor(600851475143));

The answer is: 6857. As each integer can be represented (factorized) using prime numbers such as 2^a*3^b*5^c…. We can skip prime testing and just use a simple loop to search for the largest prime factor.

1
2
3
4
5
6
7
8
9
10

function largestPrimeFactor(n) {
    let i = 2;
    while (i * i < n) {
        while (n % i == 0) {
            n /= i;
        }
        i ++;
    }
    return n;
}
function largestPrimeFactor(n) {
    let i = 2;
    while (i * i < n) {
        while (n % i == 0) {
            n /= i;
        }
        i ++;
    }
    return n;
}

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
3 Reasons to Geek Out on Your Blog　 The Terminal Software Engineer Level　 Facebook Interview Tips and Guidance　 Book Review: Python for Kids, for Dummies　 Find the Least Number Sums of Perfect Squares　 Algorithms to Sum of All Odd Length Subarrays　 Algorithm to Compute the Largest Triple Products from Array　 Algorithm to Split a Number Array into Two Balanced Parts by Usi　 Is QBasic good for Teaching Kids Programming?　 Accidentally Damaging the Graphic Card by Putting Heatsink Coppe　
评论列表
添加评论