백준 1456번 [거의 소수](C++) -yes6686- 티스토리

백준 문제 풀이: 1456 (거의 소수)

---

문제 링크: https://www.acmicpc.net/problem/1456

문제 설명:

주어진 범위 [a, b] 내에서 **"거의 소수"**의 개수를 구하는 문제입니다. - **거의 소수**: 소수의 거듭제곱 수로, 범위 내에 존재하는 값을 의미합니다. - 예를 들어, 2의 거듭제곱 4, 8, 16은 거의 소수입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int pr[10000001]; // 소수를 판별하기 위한 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // 에라토스테네스의 체: 소수 구하기
    for (int i = 2; i <= 10000000; i++) {
        pr[i] = i; // 초기화
    }

    for (int i = 2; i * i <= 10000000; i++) {
        if (pr[i] == 0) continue; // 이미 소수가 아니면 continue
        for (int j = i * i; j <= 10000000; j += i) {
            pr[j] = 0; // 소수가 아닌 수 처리
        }
    }

    long long a, b;
    cin >> a >> b; // 범위 입력

    int cnt = 0; // 거의 소수의 개수
    for (long long i = 2; i * i <= b; i++) {
        if (pr[i] == 0) continue; // 소수가 아니면 continue
        for (long long j = i * i; j <= b; j *= i) {
            if (j < a) continue; // 범위 미만이면 continue
            cnt++;
            if (j > b / i) break; // 오버플로우 방지
        }
    }

    cout << cnt; // 거의 소수의 개수 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 에라토스테네스의 체: - 소수를 구하기 위해 **에라토스테네스의 체**를 사용합니다. - pr[i]에 소수만 남기고 나머지는 0으로 설정합니다.
• 거의 소수의 판별: - 각 소수 i에 대해 그 **거듭제곱**을 계산합니다.
-

i * i

부터 시작해,

j *= i

로 증가시키며 범위

[a, b]

에 속하는 값을 찾습니다.
• 오버플로우 방지: - j > b / i 조건을 확인하여 오버플로우를 방지합니다.

시간 복잡도 분석

• **에라토스테네스의 체:** - 소수를 구하는 데 걸리는 시간 복잡도는 **O(N log log N)**입니다.
• **거의 소수 판별:** - 각 소수에 대해 거듭제곱을 구하므로, 시간 복잡도는 **O(N log N)**입니다.
• 최종적으로 전체 시간 복잡도는 **O(N log log N + N log N)**입니다.

---

결과

주어진 범위 내에서 **거의 소수**의 개수를 출력합니다.

• 입력 예시:

  1 1000

• 출력 예시:

  25

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!