4. 소수찾기 (프로그래머스)

가. 문제파악

 1. 유형 : 순열, 에라토스테네스 체

    -   경우의수는 항상 느끼지만 많이 헷갈리게 하는 것 같다. 

    -   모든 경우의수 구하는 것을 그려보면 최대한 깊이 들어갔다가 돌아왔다가 하는 원리이다.

    -   여기서는 모든 경우의 수가 아닌 중복없이 만들 수 있는 경우의 수를 판단해야한다.  

나. 코드 

 1. 풀이 : Vistied, 재귀

    -   boolean 배열을 활용해서 해당 숫자를 사용했는지 안했는지 판단하는 것이 중요하다

    -   에라토스테네스 체로 소수를 구하고 이를 이용해서 count를 올려준다. (false로 판단해서 조금이상하다..)

    -   숫자에 대한 중복은 허용되지 않으니 한번 만들어진 소수는 소수가 아닌걸로 해줬다.  

public static int n;
  public static char[] array;
  public static int res = 0;
  public static boolean[] prime;

  public static int solution(String numbers) {

    prime = new boolean[100_000_00];
    prime[1] = true;
    prime[0] = true;

    for(int i = 2; i<100_000_00; i++){
        if(!prime[i]){
            for (int j = i+i ; j < 100_000_00; j+=i) {
                prime[j] = true;
            }
        }
    }
      array = numbers.toCharArray();
      n = array.length;

      for(int i = 0; i < array.length; i++){
        perm(new boolean[array.length], "", 0, i);
    }

      return res;
  }



  public static void perm(boolean[] visited, String r , int dep, int idx){

      if(n == dep){
          return;
      }

      String temp = r+array[idx];
      if(!prime[Integer.parseInt(temp)]){
          System.out.println(Integer.parseInt(temp));
          res++;
          prime[Integer.parseInt(temp)] = true;
      }

      visited[idx] = true;
      for (int i = 0; i < n; i++) {
          if (!visited[i]) {
              perm(visited, temp, dep+1, i);
              visited[i] = false;
          }
      }
  }

 

 2. 기타 : 소수구하기

    -  다른사람 풀이에 좋은게 있어서 정리해둬야겠다.

    -  소수를 구할때 짝수를 빼고 약수가 있는지 없는지 찾는 방법이다.

    -  약수들의 반, 즉 제곱근은 이미 반에 대한 약수이므로 제곱근까지만 판단해주면 된다. 

  public boolean prime(int n){
      if(n%2 == 0 || n == 1) return false;

      for (int i = 3; i <= Math.sqrt(n) ; i+=2) {
        // +2하는 이유는 홀수만 확인
           if(n%i ==0) return false;
      }
      return  true;
  }