[JAVA] 소수 찾기(완전탐색)

소수 찾기에서 2부터 시작하여 해당 num의 루트 Math.sqrt(num)까지를 포함해 구하였다.

HashSet 자료구조를 이용해 개수를 구하였다.

 

import java.util.*;

class Solution {
   
    static Set<Integer> set = new HashSet<>();
    
    public int solution(String numbers) {
        int answer = 0;
        int len = numbers.length();
        boolean[] visited = new boolean[len];
        int[] choice = new int[len];
        
        for(int i=1;i<=len;i++){ // 선택 수
            perm(0,i,numbers,visited,choice);
        }
        answer = set.size();
        return answer;
    }
    
    // 소수인지 판별
    private static boolean isOK(int n){
        if(n < 2) return false;
        for(int i=2;i<=Math.sqrt(n);i++){
            if(n%i == 0) return false;
        }
        return true;
    }
    
    // 순열
    private static void perm(int cnt, int limit, String numbers, boolean[] visited, int[] choice){
        if(cnt == limit){
            String str = "";
            for(int i=0;i<limit;i++){
                str += choice[i]+"";
            }
            if(isOK(Integer.parseInt(str))) { // 소수
                System.out.println(Integer.parseInt(str));
                set.add(Integer.parseInt(str));
            }
            return;
        }
        for(int i=0;i<numbers.length();i++){
            if(visited[i]) continue;
            visited[i] = true;
            choice[cnt] = numbers.charAt(i)-'0';
            perm(cnt+1, limit, numbers, visited, choice);
            visited[i] = false;
        }
    }
}