[백준 JAVA] 1456. 거의 소수

문제 링크

---

https://www.acmicpc.net/problem/1456

접근 방법

---

1. 에라토스테네스의 체를 이용하여 소수를 구합니다.
2. b의 제곱근 보다 큰 소수는 제곱했을 때 b 보다 커지므로 b의 제곱근으로 for 문을 돌립니다.
3. 제곱할 때 오버플로우가 날 수 있기 때문에 Math.pow함수를 사용합니다.

소스 코드

---

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a, b, c, answer = 0;
        a = Long.parseLong(st.nextToken());
        b = Long.parseLong(st.nextToken());
        c = (long)Math.sqrt(b);

        boolean[] sieve = new boolean[(int)(c + 1)];
        for (int i = 2; i <= Math.sqrt(c); i++) {
            if (sieve[i]) {
                continue;
            }

            for (int j = i + i; j <= c; j += i) {
                sieve[j] = true;
            }
        }

        for (int i = 2; i <= c; i++) {
            if (sieve[i]) {
                continue;
            }

            long tmp, exp = 2;

            do {
                tmp = (long)Math.pow(i, exp++);
            } while (tmp < a);

            while (tmp <= b) {
                ++answer;
                tmp = (long)Math.pow(i, exp++);
            }
        }

        System.out.println(answer);
    }
}

코드 설명

---

b의 제곱근보다 작은 소수들을 구합니다.

구한 소수들을 a 보다 커질 때까지 N제곱해줍니다.

N 제곱한 수가 b 보다 작으면 answer++ 해줍니다.