[프로그래머스] Lv.2 소수 찾기

 

[문제]

코딩테스트 연습 - 소수 찾기 | 프로그래머스 스쿨

프로그래머스

 

 

 

[소스 코드]

import java.util.*;

class Solution {
    static boolean[] composite = new boolean[10000000];
    static boolean[] visit;
    static String input,s;
    static int n,answer;
    static Set<Integer> hs = new HashSet<>();
    public int solution(String numbers) {
        input = numbers;
        composite[0] = composite[1] = true;
        for(int i=2;i*i<=9999999;i++){
            for(int j=i*i;j<=9999999;j+=i){
                composite[j] = true;
            }
        }
        answer = 0;
        n = numbers.length();
        for(int i=1;i<=n;i++) {
            visit = new boolean[n];
            s = "";
            find(0,i,s);
        }
        return answer;
    }
    private static void find(int cnt,int maxCnt,String s){
        if(cnt==maxCnt){
            int num = Integer.valueOf(s);
            if(!composite[num] && hs.add(num)){
                answer++;
            }
            return;
        }
        for(int i=0;i<n;i++){
        	if(!visit[i]){
            	visit[i] = true;
                find(cnt+1,maxCnt,s+input.charAt(i));
                visit[i] = false;
            }
        }
    }
}