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

문제

풀이

import java.util.*;
class Solution {
    
    public static boolean isPrime(long num){
        if(num<2) return false;
        // 에라토스테네스의 체로 체크할때 절반(제곱근)까지만 가줘도 된다.
        else{
            for(int i=2; i<=(int)Math.sqrt(num); i++){
                if(num%i==0) return false;
            }
        }
        return true;
    }
    
    public int solution(int n, int k) {
        int answer = 0;
        String num = num = Integer.toString(n,k);

        String prime="";
        for(int i=0; i<num.length(); i++){
            if(num.charAt(i) != '0'){
                prime += num.charAt(i);
            }
            else if(num.charAt(i) == '0' && !prime.equals("")){
                if(isPrime(Long.parseLong(prime)) == true){
                    answer++;
                }
                prime="";
            }
        }
        
        // 마지막 남아있는 경우
        if(!prime.equals("") && isPrime(Long.parseLong(prime))==true){
            answer++;
        }
        
        return answer;
    }
}

좋은 문제다. 값의 범위가 엄청클수있기 때문에 int를 넘어설수있기에 long으로 변환해서 소수를 체크해줘야한다. 근데 이렇게 해도 1번 테케가 계속 시간초과가 발생했는데, 이 것을 찾는데 오래걸렸다.

핵심

1. 값의 범위가 엄청클수있기 때문에 int를 넘어설수있기에 long으로 변환해서 소수를 체크해줘야한다.
2. 에라토스테네스의 체 방식으로 소수를 판별할때 시간을 줄이기 위해서는 해당 num의 제곱근 범위까지만 for문을 돌려서 약수가 있는지 체크해줘도 된다. 이렇게 해야 효율이 좋다.

제곱근 => Math.sqrt();