[백준 1747] 소수&팰린드롬 (JAVA)

백준 1747번 문제  - 소수&팰린드롬

1747번: 소수&팰린드롬

---

문제 분석

 

• N을 넘는 수 중에서, 소수이면서 팬린드롬인 수 중 가장 작은 수를 찾아 출력해라.

---

해결 키 포인트

 

• 정수론: 소수구하기 - 에라토스테네스의 체의 원리
• 배열의 사이즈를 어떻게 설정할 것인가?
  • N은 1 ≤ N ≤ 1,000,000로 이루어진다 → 그러니 배열을 사이즈를 1,000,000로 해서 1,000,000^2의 소수를 알아내기로 정함
• 팬린드롬을 어떻게 판단하는가 - 문자열로 변환하여 비교한다
  • String.valueOf(nums[i])

 

---

에라토스테네스의 체의 원리

소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. ( 1도 소수가 아니다 ) 

 

에라토스테네스의 체 원리 알고리즘

 

1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성

2. 2부터 시작해 N의 제곱근까지 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다

3. 2~N의 제곱근 까지 탐색을 반복한 후 배열에서 남아있는 모든 수를 출력

 

N의 제곱근까지만 탐색하는 이유

N이 a*b라고 가정했을 때, a와 b 모두 N의 제곱근보다 클 수 없다. 따라서 N의 제곱근까지만 확인해도 전체 범위의 소수를 판별할 수 있다. 
만약 16의 범위까지 소수를 구할 때 16 = 4*4로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게된다는 뜻
따라서 4까지만 확인하고 소수 판별을 진행하면 된다.

---

코드

import java.util.Scanner;

public class Main {

    public static long [] nums;
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);

        // N 입력
        int N = sc.nextInt();

        // 배열 생성
        nums = new long[10000001];
        for(int i=0;i<10000001;i++) {
            nums[i] = i;
        }

        // 소수 구하기
        for(int i=2;i<10000001;i++) {
            if(nums[i] > 1) {
                distinction(i);
            }
        }

        // N 이상의 값 중에서 소수이면서 팰린드롬 수 구하기
        for(int i=N;i<10000001;i++) {
            // 소수인지 판단
            if(nums[i] > 1) {
                // 팰린드롬 수인지 판단하기 위해 문자열로 변환
                String s = String.valueOf(nums[i]);

                // 팰린드롬 수인지 알려주는 변수
                boolean isPalindrome = true;
                // 문자열의 앞글자와 끝글자 비교
                for(int j=0;j<=s.length()/2;j++) {
                    // 두 글자가 다를 경우 isPalindrome를 false로
                    if(s.charAt(j) != s.charAt(s.length()-j-1)) {
                        isPalindrome = false;
                        break;
                    }
                }
                // 팰린드롬 수일 경우 출력 후 반복 종료
                if(isPalindrome) {
                    System.out.println(nums[i]);
                    break;
                }
            }
        }
    }

    public static void distinction(int i) {
        for(int j=i+i;j<10000001;j=j+i) {
            nums[j] = 0;
        }
    }
}