백준 1456 [거의 소수] 파이썬

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

 

이 문제 생각보다 되게 어려웠다. 에라스토테네스의 체를 이용하려고 배열을 생성하려고 하니, 메모리 초과가 발생해서 순간 멍 해졌다.

이것저것 도전해보다가 결국 모르겠어서 GPT의 도움을 받았다.

1) 에라스토테네스의 체를 B까지 꼭 구현할 필요 없이, sqrt(B)+1까지만 구현하고 이에대해 소수 판별을 하면 된다.

2) 소수의 제곱이 범위내에 있는지 확인하면 된다.

#백준 1456 거의 소수
import math

A, B = map(int, input().split())

# **1. 에라토스테네스의 체를 이용한 소수 판별 (O(N^0.5))**
def sieve(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False  # 0과 1은 소수가 아님

    for i in range(2, int(math.sqrt(limit)) + 1):
        if is_prime[i]:  # i가 소수라면
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False  # i의 배수는 모두 소수가 아님

    return [num for num in range(2, limit + 1) if is_prime[num]]

# **2. 소수를 이용한 '거의 소수' 찾기**
primes = sieve(int(math.sqrt(B)))  # B의 제곱근까지만 소수 구하기
count = 0

for prime in primes:
    power = prime * prime  # 소수의 제곱부터 시작
    while power <= B:
        if power >= A:
            count += 1
        if power > B // prime:  # 오버플로우 방지
            break
        power *= prime

print(count)

갈길이 멀다..