문제

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

풀이

테스트 케이스에서 런타임 에러가 났다.

	/**
    * 조건에 맞는 소수
    * 
    * @param n 양의 정수
    * @param k k진수
    * @return
    */
   public static int solution(int n, int k) {
       String[] numbers = Integer.toString(n, k).split("0");
       int answer = 0;
       for (String x : numbers) {
           if (x.equals("1") || x.equals("")) {
               continue;
           }
           boolean isPrime = isPrime(Integer.parseInt(x));
           if (isPrime) {
               answer++;
           }
       }
       return answer;
   }

   public static boolean isPrime(int n) {
       for (int i = 2; i < n / 2; i++) {
           if (n % i == 0) {
               return false;
           }
       }
       return true;
   }

아무래도 isPrime 에서 시간초과가 나는 것 같다.
최적화 해보자

1. for 문 반복은 n / 2 보다 Math.sqrt(n) 을 사용한다. 루트 까지만 검사해봐도 해당 값이 소수인지 판별 할 수 있다

2. 조건에서 주어진 1 ≤ n ≤ 1,000,000, 3 ≤ k ≤ 10 를 커버 하기위해서는 long 형을 사용해야 한다. (제발)

	/**
     * 조건에 맞는 소수
     * 
     * @param n 양의 정수
     * @param k
     * @return
     */
    public static int solution(int n, int k) {
        String[] numbers = Integer.toString(n, k).split("0");
        int answer = 0;
        for (String x : numbers) {
            if (x.equals("1") || x.equals("")) {
                continue;
            }
            boolean isPrime = isPrime(Long.parseLong(x));
            if (isPrime) {
                answer++;
            }
        }
        return answer;
    }

    public static boolean isPrime(long n) {
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

전체 코드

전체 코드