#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/divisibility-primes/largest-prime-factor-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/divisibility-primes/largest-prime-factor-implementation

Repovive

Largest Prime Factor - Implementation - Divisibility & Primes | Math Fundamentals | Repovive

Repovive.

Math Fundamentals18 sections · 842 units13h total

Open in Course

Largest Prime Factor - Implementation

The pseudocode

Here is the full solution:


function largestPrimeFactor(n)
    largestFactor := 1
    i := 2
    while i * i <= n
        while n mod i = 0
            largestFactor := i
            n := n / i
        i := i + 1
    if n > 1 then
        largestFactor := n
    return largestFactor

Time: $O(\sqrt{n})$ . Space: $O(1)$ . The inner while loop divides out all occurrences of each prime factor before moving to the next.