Question

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

Answer 1

package main

import (
    "fmt"
)

func largestPrimeFactor(n int) int {
    div := 2
    maxPFact := -1

    for n != 0 {
        if n%div != 0 {
            div++
        } else {
            maxPFact = n
            n /= div // Integer division
            if n == 1 {
                break
            }
        }
    }

    return maxPFact
}

func main() {
    fmt.Println(largestPrimeFactor(124))  // 2 x 2 x 31
    fmt.Println(largestPrimeFactor(288))  // 2 x 2 x 2 x 2 x 2 x 3 x 3
    fmt.Println(largestPrimeFactor(1288)) // 2 x 2 x 2 x 7 x 23
    fmt.Println(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

package main

import (
    "fmt"
)

// Returns the largest prime factor of n
func largestPrimeFactor(n int64) int64 {
    largest := int64(-1)

    // Step 1: Remove all factors of 2
    for n%2 == 0 {
        largest = 2
        n /= 2
    }

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

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

    return largest
}

func main() {
    n1 := int64(124)         // 2 x 2 x 31
    n2 := int64(288)         // 2 x 2 x 2 x 2 x 2 x 3 x 3
    n3 := int64(1288)        // 2 x 2 x 2 x 7 x 23
    n4 := int64(100000000)   // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5
    n5 := int64(600851475143) // 71, 893, 1471, 6857

    fmt.Println("Largest prime factor:", largestPrimeFactor(n1))
    fmt.Println("Largest prime factor:", largestPrimeFactor(n2))
    fmt.Println("Largest prime factor:", largestPrimeFactor(n3))
    fmt.Println("Largest prime factor:", largestPrimeFactor(n4))
    fmt.Println("Largest prime factor:", largestPrimeFactor(n5))
}



/*
run:

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

*/

 

70+ SQL courses for beginners and professionals