[백준 1456] 거의 소수 Python 풀이

[백준 1456] 거의 소수 Python 풀이

📌 문제 분석

이 문제는 주어진 범위 내에서 소수의 거듭제곱의 개수를 구하는 문제입니다. 주어진 범위 [left, right]에서 소수의 거듭제곱으로 나타낼 수 있는 숫자들이 몇 개인지 구해야 합니다.

핵심 포인트

• 소수의 거듭제곱이란, 소수를 n번 곱한 수들을 의미합니다. 예를 들어, 2^1, 2^2, 3^2, 3^3 등이 해당됩니다.
• 이 문제는 범위가 10^7까지 주어지기 때문에 효율적으로 소수를 구하는 방법이 필요합니다.

🚨 시행착오

처음에는 소수를 구하는 방식과 거듭제곱을 구하는 방식에서 몇 가지 문제에 직면했습니다.

처음 코드의 문제점

• 초기에는 소수 구하는 방법이 효율적이지 않았고, 범위가 커서 실행 시간이 오래 걸렸습니다.
• 거듭제곱을 구할 때 한 번에 범위 내에 포함되는 모든 값을 체크하는 방법을 구현하려고 했으나, 이는 너무 비효율적이었습니다.

어떻게 고쳤나요?

• 소수를 구하는 방법을 에라토스테네스의 체를 사용하여 효율적으로 수정했습니다.
• 소수의 거듭제곱을 구할 때, 소수의 거듭제곱이 주어진 범위 내에 포함되는지 체크하는 방식으로 개선했습니다.

💡 해결 방안

import math

input = open("input.txt", "r").readline

left, right = map(int, input().split())
A = [0] * (10000001)

# 에라토스테네스의 체로 소수 구하기
for i in range(2, len(A)):
    A[i] = i

for i in range(2, int(math.sqrt(len(A)) + 1)):
    if A[i] == 0:
        continue
    for j in range(i * i, len(A), i):
        A[j] = 0

count = 0

# 소수의 거듭제곱을 구하고 범위 내에 있는지 체크
for i in range(2, 10000001):
    if A[i] != 0:
        temp = A[i]
        while A[i] <= right / temp:
            if A[i] >= left / temp:
                count += 1
            temp *= A[i]

print(count)

🎯 이 문제의 핵심 포인트

1. 에라토스테네스의 체를 이용해 범위 내의 소수를 효율적으로 구함.
2. 소수의 거듭제곱을 구할 때, 그 값이 주어진 범위 [left, right]에 포함되는지 체크함.
3. 배수 처리 방식을 통해 소수의 거듭제곱에 해당하는 수만 추출.
4. 주어진 범위가 매우 크기 때문에 시간 복잡도를 고려하여 해결 방안을 세심하게 설계함.

📝 예제로 이해하기

예제 입력:

1 100

예제 출력:

 

5

설명:

• 1부터 100까지의 소수의 거듭제곱으로 나타낼 수 있는 수는 2^2, 2^3, 3^2, 5^2, 7^2 총 5개입니다.

✨ 이번 문제를 통해 배운 점

1. 에라토스테네스의 체를 사용하여 소수를 빠르게 구하는 방법을 다시 한번 복습.
2. 소수의 거듭제곱을 구할 때 범위 내에 포함되는지 효율적으로 체크하는 방법.
3. 큰 범위에서 효율적인 알고리즘 설계의 중요성을 배움.

🔍 코드 설명

• A 배열은 1부터 10^7까지의 모든 수를 나타내는 배열로, 에라토스테네스의 체를 통해 소수만 남기고 나머지는 0으로 처리합니다.
• 소수의 거듭제곱을 계산할 때, A[i]가 소수라면 이를 거듭제곱하여 범위 내에 포함되는지를 확인하고, 포함되면 카운트합니다.

결론

소수의 거듭제곱을 구하는 문제는 소수를 효율적으로 구하는 알고리즘이 핵심입니다. 에라토스테네스의 체를 이용해 소수를 구하고, 이를 거듭제곱하여 범위 내에 포함되는지 체크하는 방식으로 문제를 해결할 수 있었습니다.