[프로그래머스] [JAVA] [Level 2] [2022 KAKAO BLIND RECRUITMENT] k진수에서 소수 개수 구하기

---

---

1. 에라토스테네스 체 알고리즘

import java.util.*;

class Solution {
    // 에라토스 테네스 체 
    public static boolean Eratos(long n){
        int a = (int) n;
        boolean arr[] = new boolean[a+1];
        Arrays.fill(arr, true);
        arr[0] = arr[1] = false;
        
        for(int i=2; i<=Math.sqrt(n); i++){
            if(arr[i]) {
                int j=2;
                while(i*j<=n){
                    arr[i*j] = false;
                    j += 1;
                }
            }
        }
        
        if(arr[a]) return true;
        else return false;    	
    }
        
    public int solution(int n, int k) {
       
        int answer = 0;
        // 정수 n을 k진수로
        String jinsu = Integer.toString(n, k);
        
        // 0을 기준으로 잘라서 배열에 넣기
        String sarr[] = jinsu.split("0");
 
        for(int i=0; i<sarr.length; i++){
            if(!sarr[i].equals("")) {
                long num = Long.parseLong(sarr[i]); 
                if(Eratos(num)) answer++;
            }
            
        }                
        return answer;
    }
}

• 1, 11번 런타임 에러
• 1 ≤ n ≤ 1,000,000 
• n을 k진수로 변환했을때 나오는 문자열의 길이가 지나치게 커짐
• 지나치게 큰 수에 에라토스테네스의 체 알고리즘을 사용하면 효율성이 떨어지기 때문에 시간초과 발생

 

 

 

2. 소수판별 알고리즘

import java.util.*;

class Solution {
     
    // 소수 판별 
    public static boolean check(long x){
        // 1과 0은 소수x
        if (x<=1) return false;
        
        for(int i = 2; i <= Math.sqrt(x); i++){
            if(x % i == 0)
                return false;
        }
        return true;
    }
        
    public int solution(int n, int k) {
       
        int answer = 0;
        // 정수 n을 k진수로
        String jinsu = Integer.toString(n, k);
        
        // 0을 기준으로 잘라서 배열에 넣기
        String sarr[] = jinsu.split("0");
 
        for(int i=0; i<sarr.length; i++){
            if(!sarr[i].equals("")) {
                long num = Long.parseLong(sarr[i]); 
                if(check(num)) answer++;
            }
            
        }
                
        return answer;
    }
}

• 통과

---

• Integer.toString(n, k) // 정수 n을 k진수로
• Integer.parseInt(i, N) // N진법 -> 10진법
• Integer.toBinaryString(number) // 10진법 -> 2진법
• Integer.toOctalString(number) // 10진법 -> 8진법
• Integer.toHexString(number) // 10진법 ->16진법