프로그래머스 - k진수에서 소수 개수 구하기

프로그래머스 - k진수에서 소수 개수 구하기

 

 

 문제 설명

 

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

 

 

 

 나의 풀이

 

에라토스테네스의 체를 이용해보고, 그냥 주어진 수만큼만 소수의 개수를 찾아도 보았지만 시간초과가 났다.

생각해보면 1,000,000정도의 수가 3진수로 변환되었을 때 크기는 상당히 크기 때문에 이를 전부 탐색하면서 소수를 구하는 것은 다소 무리가 있을 수 있다.

 

특정 수가 소수인지 아닌지를 탐색할 때는 제곱근까지만 탐색하면 알 수 있다.

예를 들어 12라는 수의 약수를 살펴보면 1, 2, 3, 4, 6, 12가 있는데 12의 제곱근인 Int(3.xx)에  1을 더해 4까지만 돌면 소수인지 아닌지 확인할 수 있다.(2는 6과, 3은 4와 짝지어지기 때문) 

 

import Foundation

func isPrime(_ num: Int) -> Bool {
    if num <= 1 { return false }
    for i in 2..<Int(sqrt(Double(num)))+1 {
        if num % i == 0 {
            return false
        }
    }
    return true
}

func solution(_ n:Int, _ k:Int) -> Int {
    
    let changeKnum = String(n, radix: k)
    let numArr = changeKnum.split(separator: "0")
    var cnt = 0
    for x in numArr {
        if isPrime(Int(x)!) {
            cnt += 1
        }
    }
    
    return cnt
}