소수 판별하는 메서드 (프로그래머스 k진수에서 소수 개수 구하기)

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

프로그래머스

문제를 풀다보니 다 좋은데 하나가 시간초과가 나온다.

내가하는 소수판별 코드는 2부터 해당수-1 까지 나누어떨어지는 수가 있으면 소수가 아니라는 것인데

이걸 다 반복문으로 돌리자니 오래걸리나보다.

그렇다면 어떻게 하지.. 결국 찾아봤다. 

해답은 

Math.sqrt(num)

 

2부터 (int)Math.sqrt(num) 까지 포함해서 나누어 떨어지는 지 확인하고 나누어 떨어지지 않으면 소수이다.

// k 진수로 바꾸는 메서드
// 소수 판별하는 메서드
// 0이 들어가지 않는 수 골라내는 메서드
class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        String[] numbers = change(n,k).split("0");
        for(String x : numbers){
            
            if(x.length()==0) continue;
            if(isSosu(Double.valueOf(x))) answer++;
        }
        
        return answer;
    }
    public String change(int num,int k){// k진수로 바꾸는 메서드
        if(k==10) return num+"";
        StringBuilder sb = new StringBuilder();
        while(num!=0){
            sb.append(num%k);
            num/=k;
        }
        return sb.reverse().toString();
    }
    
    public boolean isSosu(Double num){ // 소수판별
        if(num==1) return false;
        for(int i=2;i<=(int)Math.sqrt(num);i++){
            if(num%i==0) return false;
        }
        return true;
    }
}