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

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

코딩테스트 연습 - k진수에서 소수 개수 구하기

 

생각보다 오래걸렸던 문제..

자바에서는 소수를 구할때  i*i <= k 를 하면 시간초과가 나는구나.

Math.sqrt(k) 를 쓰는 버릇을 들이도록 하자!

import java.util.*;
class Solution {
   public boolean checkPrime(long k) {
        if(k==1) return false;
        else if(k==2) return true;
        int limit = (int) Math.sqrt(k);
        for(int i=2; i<=limit; ++i) {
            if(k % i == 0) {
                return false;
            }
        }
        return true;
    }
  public int solution(int n, int k) {
        int answer = 0;

        String temp[] = Integer.toString(n, k).split("0");
        for (int i=0; i<temp.length; i++) {
            if(temp[i].length() > 0 && checkPrime(Long.parseLong(temp[i]))) answer++;
        }
         return answer;
    }
}