프로그래머스 소수찾기

풀이과정

---

순열 + 소수찾기 이다. 에라토스텔레스의 체 + 순열 공식으로 풀수 있다.

---

코드

---

import java.util.*;
class Solution {
    private static int[]arr;
    public int solution(String numbers) {
        int answer = 0;
        HashSet<Integer>set = new HashSet<>();
        
        permu("", numbers, set);
        
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) answer++;
            if(a%2!=0 && isPrime(a)){
                answer++;
            }
        }
        
        return answer;
    }
    private void permu(String a, String str , HashSet<Integer>set){
        int n = str.length(); // str 은 17 n은 2
        if(!a.equals("")){
            set.add(Integer.valueOf(a));
        }
        for(int i = 0; i<n ; i++){
            permu(a+str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
        }
        
    }
    
    private boolean isPrime(int n){
        if(n==0|| n==1){
            return false;
        }
        for(int i = 3; i<(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }
}