What is the largest prime factor of the number 600851475143 ?

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

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

推荐阅读：
The Art of the Perfect Listicle　 Tools and Resources to Help Create Your Next Content Calendar　 5 Tips for Capturing More Leads on Your Blog　 Don’t Fall Victim to the Content Overproduction Trap　 Are You Taking Advantage Of These Free WordPress Marketing Plugi　 What Content Marketers Can Learn from Game of Thrones　 All You Need To Know About How Small Business Should Handle Soci　 Should You Add Live Chat to Your Blog?　 Food Blogger Accuses Fast Food Giant Of Stealing His Recipe　 Back To School 2016: How To Rock (And Profit) With Sales And Mar　
评论列表
添加评论