https://school.programmers.co.kr/learn/courses/30/lessons/42839
1. String을 순열을 통해 여러 조합의 숫자로 만들어줘야함
"17" -> 1,7,17,71
2. 만든 숫자를 소수체크를 해야함
isPrime 함수 구현
소수 판별하는 함수를 만드는 방법은 두가지이다.
- 자연수를 나눠보는 것
public static boolean isPrime(int n){
if(n==1||n==0) return false;
for(int i=2;i<Math.sqrt(n);i++){
if(n%i==0) return false;
}
return true;
}여기서 Math.sqrt를 쓴 이유는 무조건적으로 이 범위안에서 n의 약수가 있기 때문이다.
예를 들어 16일경우
116 -> 소수 제외
28
44
82
16*1 -> 소수 제외
Math.sqrt이하에서 16이 소수인지 아닌지 판별할 수 있다.
그렇기 때문에 시간 복잡도를 아끼기위해 Math.sqrt이하만큼 반복문을 돌린다.
- 에라토스테네스의 체
어떤 범위만큼 소수를 구해야한다면 에라토스테네스의 체를 사용하는게 효율적이다.
에라토스테네체는 2의 배수 3의 배수....를 모두 지워주며 소수를 찾는 방법이다.
체에서 걸러낸다고 생각하면 된다.
prime[0] = prime[1] = true;
// 제곱근 함수 : Math.sqrt()
for(int i = 2; i <= Math.sqrt(N); i++) {
// 이미 체크된 배열이면 다음 반복문으로 skip
if(prime[i] == true) {
continue;
}
// i 의 배수들을 걸러주기 위한 반복문
for(int j = i * i; j < prime.length; j = j+i) {
prime[j] = true;
}
}정답 코드
import java.util.*;
class Solution {
static int[] list=new int[10000001];
static int cnt=0;
static HashSet<Integer> set=new HashSet<>();
public static void permutation(String numbers,String output,int depth,boolean[] visited){
if(output!=""){
int number=Integer.parseInt(output);
if(isPrime(number)) set.add(number);
}
if(depth==numbers.length()) return;
for(int i=0;i<numbers.length();i++){
if(!visited[i]){
visited[i]=true;
permutation(numbers,output+numbers.charAt(i),depth+1,visited);
visited[i]=false;
}
}
}
public static boolean isPrime(int n){
if(n==1||n==0) return false;
for(int i=2;i<Math.sqrt(n);i++){
if(n%i==0) return false;
}
return true;
}
public int solution(String numbers) {
int answer = 0;
list[0]=1;
list[1]=1;
boolean[] visited=new boolean[numbers.length()];
permutation(numbers,"",0,visited);
return set.size();
}
}