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) —
GD Star Rating
loading...
245 wordsloading...
Last Post: Can we Construct K Palindrome Strings?
Next Post: Find the largest palindrome From the product of two 3-digit numbers
