TIL #58

k진수에서 소수 개수 구하기

주어진수 n을 k진법으로 바꿨을때 조건을 만족하는 소수를 구하며 총 소수의 개수를 리턴해야 한다.

toString을 이용해서 n을 k진법으로 바꿔준후 0을 기준으로 split해서 반환된 배열의 요소가 비어있지 않고 1이상의 소수이면 answer를 카운트 해주도록 풀었다.

---

나의 코드

class Solution {
    fun solution(n: Int, k: Int): Int {
        var answer: Int = 0
        var nSplit = n.toString(k).split("0")
        for(i in nSplit){
            if(i.isNotEmpty() && i.toLong() > 1 && prime(i.toLong())){
                        answer++
            }
        }
        return answer
    }
    
    fun prime(i: Long): Boolean{
        var sqrt = Math.sqrt(i.toDouble()).toLong()
        for(j in 2L..sqrt){
            if( i % j == 0L){
                return false
            }
        }
        return true
    }
}

처음 풀이에서 배열의 요소가 커질 경우 오류가 나서 Int에서 Long으로 바꿔주고 prime함수에 sqrt를 추가해주었다.

---

다른사람의 코드

import java.math.*
class Solution {

    fun solution(n: Int, k: Int): Int {
        var answer: Int =0
        val newN = n.toString(k).split("0")
        for(i in newN) {
            if(i == "" || i == "0" || i == "1") continue
            if(BigInteger(i).isProbablePrime(1)) answer ++
        }
        return answer
    }
}