몇 블로그 설명이 내가 생각하는 풀이와 설명이 다른것 같아서 기초부터 따로 정리했다.
- 소수란) "1보다 큰" 자연수 중 1과 자기 자신만을 약수로 가지는 수다
- 소수판정 방법)
소수 판별을 위해 n의 제곱근까지만 확인하면 된다.
즉, n자리수의 값X를을 i=1 ~ X의 제곱근까지 for loop를 돌려서 if( X%i == 0 ) 이 true이 나오면 소수가 아니다.
for (int i=2; i<=Math.sqrt(num); i++) {
if (num % i == 0) return false;
}이 이유는 소수는 1과 자기자신을 제외한 수로 나눠지면 안된기 때문이다.
소수 찾기는 에라토스테네스의 체라는 방법이 있고 시간복잡도는 O(nloglogn)를 가진다.
N=10^8인 경우, 이는 4초가 걸려 2초 안에 해결할 수 없을 뿐더러, 애초에 처음부터 배열 선언시에 메모리 초과가 뜰것이다.
소수판별 방법을 위해 에라토스테네스를 사용하지 않도록 한다.
에라토스테네스는 1~N 자리수의 값까지의 모든 수를 판별한다. O(nloglogn).
N의 사이즈가 너무 커서, 이 대신, 제곱근까지만 확인하는 위의 소수판정 방법을 사용한다.
*
백준 신기한 소수 문제는 주어진 N 자리수의 가능한 모든 소수를 찾는것이다.
주의점은 단순하게 각 자리에 소수가 있다고 해당 숫자가 소수는 아니다.
ex) 1333 의 약수는 1, 31, 43, 1333 이다.
그래서, 완전탐색으로 모든 경우의 수를 구한다.
즉, 각 자리에 0~9의 숫자를 추가하여 N자리수만큼 만드는 모든 조합을 만들고, 해당 값의 위 소수판정 방법을 사용한다.
public static void getResult(int output, int n) {
if (n == 0) {
if (isPrime(output)) sb.append(output).append("\n");
return;
}
for (int i=0; i<10; i++) {
int next = output*10+i;
if (isPrime(next)) getResult(next, n-1);
}
}
그럼, N=4 인 경우, 값이 0000 부터 시작한다.
소수의 정의에 따라, 2 이상인 값만 처리할 수 있도록 2이하인 값은 건너뛰도록 한다. ( ex. 0,1 )
2 이상인 값들만 소수 판정하여 맞다면 true를 반환하여 해당 값을 StringBuilder에 추가하고 마지막에 모든 값들을 출력해주면 답이 완성된다.
public static boolean isPrime(int num) {
if (num < 2) return false;
for (int i=2; i<=Math.sqrt(num); i++) {
if (num % i == 0) return false;
}
return true;
}
최종코드)
* 코드 출처: https://velog.io/@jslog/BOJ-백준-2023번-신기한-소수-자바-JAVA-1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
getResult(0,n);
System.out.println(sb);
}
public static void getResult(int output, int n) {
if (n == 0) {
if (isPrime(output)) sb.append(output).append("\n");
return;
}
for (int i=0; i<10; i++) {
int next = output*10+i;
if (isPrime(next)) getResult(next, n-1);
}
}
public static boolean isPrime(int num) {
if (num < 2) return false;
for (int i=2; i<=Math.sqrt(num); i++) {
if (num % i == 0) return false;
}
return true;
}
}
