2월 27일 TIL

프로그래머스 코딩테스트 [ k 진수에서 소수 개수 구하기 ]

Github 링크

• 이 문제도 크게 어려운것은 없으나, 주의 해야할 점은, 시간 초과문제이다.
• 소수 구할때 그냥 brute force로 구하게 되면 시간 초과가 뜰 가능성이 있다.
• 따라서 2 부터 sqrtNumber 까지만 확인하는 작업을 한다.
• 여기서 문제가 생겼다. 사실 sqrtNumber 까지가 아니라 sqrtNumber +1 까지 해야한다.

import Foundation

func solution(_ n:Int, _ k:Int) -> Int {
    let baseString = String (n, radix:k)
    var numberString = baseString.split(separator:"0")
    var ans = 0
    
    
    for temp in numberString {
        let num = Int(temp)!
        if isPrime(num){
            ans += 1
        }
    }
    return ans
    
}

func isPrime(_ number: Int) -> Bool {
    if number <= 1 {
        return false
    }
    if number == 2 {
        return true
    }
    let sqrtValue = Int(Double(number).squareRoot()) + 1
    for divisor in 2...sqrtValue {
        if number % divisor == 0 && divisor != number{
            return false
        }
    }

    return true
}