Question

How to find the largest prime factor of a number in TypeScript

Answer 1

function largestPrimeFactor(n: number) {
    let div: number = 2;
    let maxPFact: number = -1;

    while (n !== 0) {
        if (n % div !== 0) {
            div++;
        } else {
            maxPFact = n;
            n = Math.floor(n / div); // Integer division
            if (n === 1) {
                break;
            }
        }
    }

    return maxPFact;
}

console.log(largestPrimeFactor(124));  // 2 x 2 x 31
console.log(largestPrimeFactor(288));  // 2 x 2 x 2 x 2 x 2 x 3 x 3
console.log(largestPrimeFactor(1288)); // 2 x 2 x 2 x 7 x 23
console.log(largestPrimeFactor(100000000)); // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5

  
  
/*
run:
 
31 
3 
23 
5 

*/

 

70+ SQL courses for beginners and professionals

Answer 2

// Returns the largest prime factor of n
function largestPrimeFactor(n: bigint): bigint {
    let largest: bigint = -1n;

    // Step 1: Remove all factors of 2
    while (n % 2n === 0n) {
        largest = 2n;
        n /= 2n;
    }

    // Step 2: Try odd factors from 3 to sqrt(n)
    let i: bigint = 3n;
    while (i * i <= n) {
        while (n % i === 0n) {
            largest = i;
            n /= i;
        }
        i += 2n;
    }

    // Step 3: If n is still > 2, it is a prime number
    if (n > 2n) {
        largest = n;
    }

    return largest;
}

const n1 = 124n; // 2 x 2 x 31
const n2 = 288n; // 2 x 2 x 2 x 2 x 2 x 3 x 3
const n3 = 1288n; // 2 x 2 x 2 x 7 x 23
const n4 = 100000000n; // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5
const n5 = 600851475143n; // 71, 893, 1471, 6857

console.log("Largest prime factor:", largestPrimeFactor(n1));
console.log("Largest prime factor:", largestPrimeFactor(n2));
console.log("Largest prime factor:", largestPrimeFactor(n3));
console.log("Largest prime factor:", largestPrimeFactor(n4));
console.log("Largest prime factor:", largestPrimeFactor(n5));



/*
run:

Largest prime factor: 31n
Largest prime factor: 3n
Largest prime factor: 23n
Largest prime factor: 5n
Largest prime factor: 6857n

*/

 

70+ SQL courses for beginners and professionals