Question

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

Answer 1

import Foundation

func largestPrimeFactor(_ n: Int) -> Int {
    var num = n
    var div = 2
    var maxPFact = -1

    while num != 0 {
        if num % div != 0 {
            div += 1
        } else {
            maxPFact = num
            num /= div // Integer division
            if num == 1 {
                break
            }
        }
    }
    
    return maxPFact
}

print(largestPrimeFactor(124))  // 2 x 2 x 31
print(largestPrimeFactor(288))  // 2 x 2 x 2 x 2 x 2 x 3 x 3
print(largestPrimeFactor(1288)) // 2 x 2 x 2 x 7 x 23
print(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

import Foundation

// Returns the largest prime factor of n
func largestPrimeFactor(_ n: Int64) -> Int64 {
    var num = n
    var largest: Int64 = -1

    // Step 1: Remove all factors of 2
    while num % 2 == 0 {
        largest = 2
        num /= 2
    }

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

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

    return largest
}

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

print("Largest prime factor:", largestPrimeFactor(n1))
print("Largest prime factor:", largestPrimeFactor(n2))
print("Largest prime factor:", largestPrimeFactor(n3))
print("Largest prime factor:", largestPrimeFactor(n4))
print("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