오늘의 알고리즘 - 백준 1546, 1747 자바 ( 에라토스테네스의 체)

1. 거의 소수

public static class BOJ1456{
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            long min = Long.parseLong(st.nextToken());
            long max = Long.parseLong(st.nextToken());
            long[] arr = new long[10000001];

            // 초기화
            for (int i = 2; i < arr.length; i++) {
                arr[i] = i;
            }

            // 에라토스테네스의 체
            for (int i = 2; i <= Math.sqrt(arr.length); i++){
                if (arr[i] == 0){
                    continue;
                }
                for (int j = i + i; j < arr.length; j += i) {
                    arr[j] = 0;
                }
            }

            int count = 0;
            for (int i = 2; i < arr.length; i++) {
                if (arr[i] != 0){
                    long temp = arr[i];
                    while ((double) arr[i] <= (double) max/temp){
                        if ((double) arr[i] >= (double) min/temp){
                            count++;
                        }
                        temp = temp * arr[i];
                    }
                }
            }

            System.out.println(count);
        }
    }

• 에라토스테네스의 체 사용하는 문제
• 까다로운것은 값이 튀는 것
• N의 k승을 구하면(arr[i]의 제곱을 구하면) long형을 초과할수도 있으므로, 이항 정리를 활용해야 한다

---

2. 소수 펠린드롬

    public static class BOJ1747 {
        static int[] arr = new int[10000001];
        public static void main(String[] args) {
            // 초기화
            for (int i = 2; i < arr.length; i++) {
                arr[i] = i;
            }

            isPrime();

            Scanner sc = new Scanner(System.in);

            int N = sc.nextInt();

            while (true) {
                if (arr[N] != 0 && isPalindrome(N)) {
                    System.out.println(N);
                    break;
                }
                N++;
            }
        }

        public static boolean isPalindrome(int N){
            String s = String.valueOf(N);
            char[] charArray = s.toCharArray();
            int startIdx = 0;
            int endIdx = s.length() - 1;

            while (startIdx < endIdx){
                if (charArray[startIdx] != charArray[endIdx]){
                    return false;
                }
                startIdx++;
                endIdx--;
            }

            return true;
        }

        public static void isPrime(){
            for (int i = 2; i < Math.sqrt(arr.length); i++) {
                if (arr[i] == 0) continue;
                for (int j = i + i; j < arr.length; j += i) {
                    arr[j] = 0;
                }
            }
        }
    }

• 소수를 찾는 매서드와 펠린드롬을 찾는 매서드를 분리했다.

• 소수는 에라토스테네스의 체

• 팰린드롬은 String -> charArray -> 인덱스비교로 찾았다

• 소수이면서, 펠린드롬이며, N보다 큰 수를 while문으로 찾다가 break.