What is the largest prime factor of the number 600851475143 ?

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

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

推荐阅读：
Cloud-Ready Infrastructure Optimization　 Freedom of Speech Isn’t So Free　 10 Things You Should Do When Starting an Online Store　 The Importance of Cybersecurity in Real Life　 The Best Productivity Trends and Hacks of 2015　 3 Great New Ways Of Generating Money With Content Online　 Local SEO 101 For Law Firms [Infographic]　 Make Sure You’re On Top of Google’s Mobile-Friendly Algorithm　 Best Tools and Apps for Travel Bloggers　 On-Page Optimization Tips to Complement Your Great Content　
评论列表
添加评论