[프로그래머스] 완전탐색: 소수찾기 (Lv2) (feat.에라토스테네스의 체)

🔎 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42839

---

📖 풀이방법

1) 전체 solution 풀이

• 재귀 함수로 모든 카드의 조합을 만들어 set에 추가한다.
• set의 숫자들 중 소수인 경우에만 count++한다.
• 소수 여부를 판단하기 위해 에라토스테네스의 체를 활용한다.

2) 모든 숫자 조합을 set에 추가한다.

• 재귀함수를 사용해 모든 숫자 조합을 set에 추가한다.
• 현재까지 만들어진 조합 comb를 set에 추가하고
• 새로운 combination을 위해 현 comb + others의 i번째 character를 조합한다.

3) 완성된 numbersSet를 하나씩 꺼내 소수인지 확인한다.

• 에라토스테네스의 체란 2-MaxNum까지 전부 배수인지 확인할 필요가 없다는 것을 증명한 수학적인 이론이다.
• 예를 들어 97이라는 숫자가 소수인지 아닌지를 확인하고 싶다면, 97이 2~96 전부의 배수인지 확인할 필요가 없고, 2~sqrt(96)의 배수인지만 확인하면 된다는 이론이다.
• 그렇기 때문에 우리도 isPrime 함수에서 전부를 보지 않고, sqrt한 값까지만 확인하고 비교한다.

---

💡에라토스테네스의 체 란?

소수를 판별하는 알고리즘이다.

소수들을 대량으로 빠르고 정확하게 구하는 방법이다.

단일 숫자 소수 여부 확인

어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.

수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다.

만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다.

에라토스테네스의 체 원리

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

배열을 생성하여 초기화한다.
2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
2부터 시작하여 남아있는 수를 모두 출력한다.

---

📌 코드

import java.util.HashSet;

class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;		// 2는 소수
            if(a%2!=0 && isPrime(a)){
                count++;
            }
        }        
        return count;
    }

    // 에라토스테네스의 체 - 소수 판별
    public 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;
    }

    public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        //if (n == 0) System.out.println(prefix);
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++)
          permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
    }
}