What is the largest prime factor of the number 600851475143 ?

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

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) —

推荐阅读：
How Facebook Can Build Or Destroy An Entrepreneur’s Career　 Top 3 Email Marketing Software for Turning Subscribers Into Cust　 Five Reasons to Get Business Funding for Your Blog　 How to Compute the Surface Area of 3D Shapes (Cubes Placed on Gr　 How to Find the Longest Harmonious Subsequence?　 How to Find the Length of Longest Fibonacci Subsequence using Br　 How to Find the Length of the Longest Increasing Subsequence usi　 Facing Heads Probabilties of Tossing Strange Coins using Dynamic　 How to Find the Missing Number In Arithmetic Progression?　 Top 5 Factors Every Attorney Must Know About Local SEO For Law F　
评论列表
添加评论