[1456] 거의 소수

✔ 거의 소수

[백준 1456]

문제 분석하기

최대 범위에 해당하는 모든 소수를 구해 놓고, 이 소수들이 입력된 A와 B 사이에 존재하는지 판단해 문제를 해결

이를 위해 에라토스테네스의 체를 이용해 빠르게 소수를 먼저 구하도록 함 

손으로 풀어보기

1. 2 ~ 10000000 사이에 존재하는 모든 소수를 구함
2. 각각의 소수에 관해 소수를 N 제곱한 값이 B보다 커질 때까지 반복문을 수행
   • 소수를 N 제곱한 값이 A보다 크거나 같으면 거의 소수로 판단해 카운트
   • N 제곱한 값을 구하는 도중 값의 범위가 long형을 초과하는 경우가 발생할 수 있으므로
     N^k과 B 값이 아니라 N과 B/N^(k-1)을 비교하는 형식을 사용

예) A = 1, B = 1000

모든 소수

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

N	거의 소수
2의 제곱	4, 8, 16, 32, 64, 128, 256, 514
3의 제곱	9, 27, 81, 243, 729
5의 제곱	25, 125, 625
7의 제곱	49, 343
11의 제곱	121
13의 제곱	169
17의 제곱	289
19의 제곱	361
23의 제곱	529
29의 제곱	841
31의 제곱	961

슈도코드 작성하기

Min(시작 수) Max(종료 수)
A(소수 배열)
for(2 ~ 10000000) {
    A 배열 초기화하기
}
for(10000000의 제곱근까지 반복하기) {
    소수가 아니면 넘어감
    for(소수의 배숫값을 10000000까지 탐색하기) {
        이 수가 소수가 아니라는 것을 표시하기
    }
}
for(2 ~ 10000000) {
    A 배열에서 소수인 값일 때
    temp = 현재 소수
    while(현재 소수 <= Max/temp) {
        if(현재 소수 >= Min/temp) 정답값 증가
        temp = temp * 현재 소수
    }
}
정답 출력하기

코드 구현하기

/**
 * 1456) 거의_소수
 */
public class D038_1456 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // Min(시작 수)
        long Min = sc.nextLong();
        // Max(종료 수)
        long Max = sc.nextLong();
        // A(소수 배열)
        long[] A = new long[10000001];
        // A 배열 초기화하기
        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;
            }
            // 소수의 배숫값을 10000000까지 탐색하기
            for (int j = i + i; j < A.length; j = j + i) {
                // 이 수가 소수가 아니라는 것을 표시하기 (배수 지우기)
                A[j] = 0;
            }
        }
        int count = 0;
        for (int i = 2; i < 10000001; i++) {
            // A 배열에서 소수인 값일 때
            if (A[i] != 0) {
                // temp = 현재 소수
                long temp = A[i];
                while ((double) A[i] <= (double) Max / (double) temp) {
                    if ((double) A[i] >= (double) Min / (double) temp) {
                        // 정답값 증가
                        count++;
                    }
                    // temp = temp * 현재 소수
                    temp = temp * A[i];
                }
            }
        }
        // 정답 출력하기
        System.out.println(count);
    }
}