[Swift 알고리즘] 백준 11653 (소인수분해)

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

 

해결 방법 : 소수 찾고 수수를 통해서 계산

 

 

func sol4() {
    let n = Int(readLine()!)!
    if n == 1 {
        return
    }
    else if n < 4 {
        print(n)
        return
    }
    var targetArr: [Bool] = Array(repeating: true, count: n + 1)
    for i in 2...Int(sqrt(Double(n))) {
        if targetArr[i] == true {
            var tempInd = i + i
            while tempInd <= n {
                targetArr[tempInd] = false
                tempInd += i
            }
        }
    }
    
    var temp = n
    while !targetArr[temp]{
        for i in 2...Int(sqrt(Double(n))) {
            if targetArr[i] == false {
                continue
            }
            if temp % i == 0 {
                temp /= i
                print(i)
                break
            }
        }
    }
    if temp != 1 {
        print(temp)
    }
}
sol4()

 

ideal한 해결방법 :

import Foundation

var input: Int = Int(readLine()!)!
var i = 2
while i * i <= input {
    while input % i == 0 {
        print(i)
        input /= i
    }
    i += 1
}

if input != 1 {
    print(input)
}