소수찾기

import java.util.HashSet;
import java.util.Iterator;

class Solution {
    HashSet<Integer> numberSet = new HashSet<>();
    public boolean isPrime(int num){
        //1. 0과 1은 소수가 아니다.
        if(num == 0 || num == 1)
            return false;
        
        //2. 에라토스테네스의 체의 limit를 계산한다.
        int lim = (int)Math.sqrt(num);
       
        //3. 에라토스테네스의 체에 따라 limit까지만 배수 여부를 확인한다.
        for(int i = 2; i <= lim; i++)
            if(num % i == 0)
                return false;
        return true;
    }
    
    public void recursive(String comb, String others){
        // 1. 현재 조합을 set에 추가한다.
        if(!comb.equals(""))
            numberSet.add(Integer.valueOf(comb));
        
        // 2. 남은 숫자 중 한 개를 더해 새로운 조합을 만든다.
        for(int i = 0; i < others.length(); i++)
            recursive(comb + others.charAt(i), others.substring(0,i) + others.substring(i+1));
    }
    
    public int solution(String numbers) {
        int count = 0;
        // 1. 모든 조합의 숫자를 만든다.
        recursive("", numbers);
        // numberSet -> [1,17,7,71]
        
        // 2. 소수의 개수만 센다.
        Iterator<Integer> it = numberSet.iterator();
        while(it.hasNext()){
            int number = it.next();
            if(isPrime(number))
                count++;
        }            
        // 3. 소수의 개수를 반환한다.
        return count;
    }

}

재귀함수 & 에라토스테네스의 체 이론을 활용.
1. 숫자조합 : 생성가능한 모든 숫자조합을 재귀함수를 통해 하나씩 만든다.
2. Set : set의 개념을 활용하여 중복되는 조합을 제거한다.
3. 소수인지 판단 : 지금 만들어진 숫자가 소수인지 판단한다.(에라토스테네스의 체)

1. iterator 개념 외우기 (hasNext, next, remove)
2. sqrt() : 제곱근
3. subustring(0,i) : 0의 자리부터 i까지의 숫자 / substring(i+1) : i+1한 자리의 숫자
4. hashSet