What is the largest prime factor of the number 600851475143 ?

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

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

推荐阅读：
味精的食用安全性及合适用量问题　 食品安全问题并不是食品添加剂的错　 温州苍南黑作坊两年产千吨剧毒湿米面　 食药监总局提醒注意保健食品五大陷阱　 对儿童健康成长有益的六大食物　 健康养生：七种常见的黑色滋补食物　 竹炭食品排毒就是一个忽悠人的概念　 中华人民共和国食品安全法(全文)　 山东启动打击非法保健食品专项行动　 盘点那些不科学不健康的饮食习惯　
评论列表
添加评论