지름길
https://www.acmicpc.net/problem/2023
2023호: 수수께끼의 소수
'추천 관련글,
수빈이는 지구상에서 가장 좋아하는 것은 소수이고 그녀의 취미는 소수를 가지고 노는 것입니다.
요즘 수빈은 소수 7331에 가장 관심이 많다.
7331도 소수지만 이상하게도 733도 소수이고 73도 소수다.
www.acmicpc.net
문제의 해석
N개의 숫자(N, N-1, N-2, N-3…가 모두 소수인 자릿수)로 수수께끼의 소수를 출력하세요.
암호
package algo.bj.g5_2023;
import java.io.*;
import java.util.*;
public class Main2 {
static StringBuilder sb;
static int N;
public static void main(String() args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
dfs(2, 1);
dfs(3, 1);
dfs(5, 1);
dfs(7, 1);
System.out.println(sb);
}
private static void dfs(int num, int digit) {
if (digit == N) {
if (isPrime(num)) {
sb.append(num + "\n");
return;
}
}
for (int i = 1; i <= 9; i+=2) {
int now = num * 10 + i;
if(isPrime(now)) {
dfs(now, digit + 1);
}
}
}
private static boolean isPrime(int num) {
if (num < 2) {
// 소수가 아님
return false;
}
if (num == 2) {
// 소수
return true;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
// 소수가 아님
return false;
}
}
// 소수
return true;
}
}
코드 해석
문제는 N-1에서 N-(N-1) 자리까지의 모든 소수 자릿수가 소수인 N 자리 소수 자릿수 중 소수를 찾는 것입니다.
여기서 주목해야 할 한 가지는 N-(N-1)이 소수인지 여부를 결정해야 한다는 것입니다.
마지막으로 N개의 소수점 자리 중 첫 번째 숫자는 소수( == N-(N-1)은 소수입니다.
) 신비한 소수로 테스트할 수 있습니다.
1의 소수는 2, 3, 5, 7개이므로 첫 번째 숫자 2, 3, 5, 7이 후보입니다.
또한 짝수는 두 번째 자리부터 2로 나누어 떨어지므로 1, 3, 5, 7, 9가 있는 숫자에 대해 소수 결정을 계속할 수 있습니다.
발생한 문제 및 솔루션
나는 에라토스테네스의 체 문제를 풀 시간이 없었다.
문제에 따라 효율적인 코드가 달라집니다!
코드는 코드 실습 편집기에서 직접 작성했습니다.
버그가 있거나 더 나은 코드 방향을 알고 있다면 의견을 남겨주세요.