문제
소수&팰린드롬
교재 풀이
import java.util.Scanner;
public class P1747_소수팰린드롬 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] A = new int[10000001]; // N의 범위까지 소수 구해주기
for (int i = 2; i < A.length; i++) {
A[i] = i;
}
for (int i = 2; i < Math.sqrt(A.length); i++) { // 제곱근 까지만 수행
if (A[i] == 0) {
continue;
}
for (int j = i + i; j < A.length; j = j + i) { // 배수 지우기
A[j] = 0;
}
}
int i = N;
while (true) { // N부터 1씩 증가시켜가면서 소수와 펠린드롬 수가 맞는지 확인
if (A[i] != 0) {
int result = A[i];
if (isPalindrome(result)) {
System.out.println(result);
break;
}
}
i++;
}
}
private static boolean isPalindrome(int target) // 펠린드롬수 판별 함수
{
char temp[] = String.valueOf(target).toCharArray();
int s = 0;
int e = temp.length - 1;
while (s < e) {
if (temp[s] != temp[e])
return false;
s++;
e--;
}
return true;
}
}
내 풀이) 24.6.20에 풀고 맞음
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args) throws IOException{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] a=new int[10000001];
for(int i=2;i<=10000000;i++){
a[i]=i;
}
for(int i=2;i<=Math.sqrt(10000000);i++){
if(a[i]!=0){
for(int j=i*i;j<=10000000;j+=i){
a[j]=0;
}
}
}
for(int i=2;i<a.length;i++){
if(a[i]!=0&&a[i]>=n){
if(isPalindrome(a[i])){
System.out.println(a[i]);
break;
}
}
}
}
public static boolean isPalindrome(int n){
char[] c=Integer.toString(n).toCharArray();
int s=0;
int e=c.length-1;
while(s<e){
if(c[s]==c[e]){
s++;
e--;
}else
return false;
}
return true;
}
}
// 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때,
// N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구해라
// 접근법
// 일단 에라토스테네스의 체로 소수 배열 a 만들어 놓고
// a를 가지고 반복하면서 팰린드롬인 거 발견되면 break하고 출력하기
// 팰린드롬 판별은 chat배열로 바꾼 후
// 투 포인터를 써서 양끝에 놓고
// 게속 같을 시 s++, e-- 해주면서 s<e일 때까지 계속 while해주는데
// s<e가 아닐 때까지 그러면 그 때의 수를 출력하면 됨
// 슈도코드
// n을 입력받고
// 에에라토스테네스의 체로 소수 배열 a 만들기
// 배열 크기는 일단 넉넉히 천만으로 해주고
// for i=2 i<=sqrt(천만) i++
// if a[i]!=0
// for j=i*i j<=천만 j+=i
// a[j]=0
// for i=2 i<a.length i++
// if a[i]!=0 && a[i]>=n
// if isPalindrome(a[i])
// a[i]를 출력
// break
// isPalindrome 함수 구현 => 인수로 int n으로 받고
// n을 문자 배열 c로 바꾸고
// s, e 인덱스를 양 끝을 가리키게 하고
// while s<e
// if c[s] == c[e]
// s++, e--
// else
// return false
// return true
설명
- 굳이 왜 a 배열 크기를 10000001으로 한 거야? 이 문제의 경우 n의 값이 백만 이하인데 말이지.
- 소수와 팰린드롬 수의 분포:
- 소수는 무한히 존재하지만, 소수이면서 팰린드롬인 숫자는 상대적으로 드물게 분포합니다. 따라서 N이 백만 이하일지라도, 해당 조건을 만족하는 소수를 찾기 위해 백만 이상의 범위까지 탐색할 필요가 있을 수 있습니다.
- 에라토스테네스의 체 범위 설정:
- 에라토스테네스의 체를 이용하여 소수를 구할 때, 넉넉한 범위를 설정해두는 것이 좋습니다. 이는 범위 내의 모든 소수를 미리 구해놓기 위해서입니다. 10,000,001까지의 소수를 구해놓으면, 소수 팰린드롬을 찾기 위해 넉넉한 범위를 탐색할 수 있습니다.
- 대안
- 만약 메모리 사용량이나 배열 크기가 걱정된다면, 코드의 효율성을 위해 소수와 팰린드롬 수를 찾는 범위를 점진적으로 늘려가는 방법을 사용할 수 있습니다.
- 초기에는 1,000,001 정도의 크기를 사용하고, 소수 팰린드롬이 발견되지 않으면 범위를 늘려가는 방식입니다.
- 이렇게 하면 초기 설정된 범위를 초과하는 경우에도 소수와 팰린드롬을 찾을 수 있습니다.
import java.util.Scanner;
public class P1747_소수팰린드롬 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int upperLimit = 10000000; // 초기 범위를 10,000,000으로 설정
int[] A = new int[upperLimit + 1]; // N의 범위까지 소수를 구해줌
// 에라토스테네스의 체로 소수 구하기
for (int i = 2; i <= upperLimit; i++) {
A[i] = i;
}
for (int i = 2; i <= Math.sqrt(upperLimit); i++) {
if (A[i] == 0) {
continue;
}
for (int j = i + i; j <= upperLimit; j += i) {
A[j] = 0;
}
}
int i = N;
while (true) { // N부터 1씩 증가시켜가면서 소수와 팰린드롬 수가 맞는지 확인
if (i > upperLimit) { // upperLimit을 초과하면 범위를 늘려야 함
upperLimit *= 2;
A = extendArrayAndRecalculatePrimes(A, upperLimit);
}
if (A[i] != 0) {
if (isPalindrome(i)) {
System.out.println(i);
break;
}
}
i++;
}
}
private static boolean isPalindrome(int target) { // 팰린드롬수 판별 함수
char[] temp = String.valueOf(target).toCharArray();
int s = 0;
int e = temp.length - 1;
while (s < e) {
if (temp[s] != temp[e]) {
return false;
}
s++;
e--;
}
return true;
}
private static int[] extendArrayAndRecalculatePrimes(int[] oldArray, int newLimit) {
int[] newArray = new int[newLimit + 1];
System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);
for (int i = oldArray.length; i <= newLimit; i++) {
newArray[i] = i;
}
for (int i = 2; i <= Math.sqrt(newLimit); i++) {
if (newArray[i] == 0) {
continue;
}
for (int j = i + i; j <= newLimit; j += i) {
newArray[j] = 0;
}
}
return newArray;
}
}