[백준/Python]1456: 거의 소수

문제

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

백준 문제집 - 0x12강 - 수학

 

알고리즘: 수학, 정수론

---

풀이

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.
두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

에라토스테네스의 체 문제다.

단, 리스트의 크기를 B에 맞춰 설정하면 메모리 초과가 난다.

 

문제를 읽어보면 "거의 소수"는 소수의 거듭제곱수다.

따라서 어떤 소수를 K라고 했을때 K * K <= B 를 만족해야하므로 소수 판별은 B의 제곱근까지만 실행하면 된다.

(이렇게 해도 메모리 사용량은 110536KB였다...^^)

 

이 외에는 특별한 로직이 필요없는 문제다.

먼저 에라토스테네스의 체 알고리즘대로 소수 판별을 하고, 해당 수를 제곱부터 곱해가며 A이상 B이하가 될 경우에만 카운트한다.

2 → 4, 8, 16...

3 → 9, 27, 81...

 

전체 코드

# 메모리: 110536KB / 시간: 3384ms
from sys import stdin


input = stdin.readline

A, B = map(int, input().split())
# 어차피 어떤 수 i가 소수일때, i*i는 B보다 같거나 작아야하므로 "소수 판정"은 B의 제곱근까지만 진행하면 된다.
root = int(B ** 0.5)

primes = [True] * (root + 1)
primes[0] = primes[1] = False
almost_prime = 0

for i in range(2, root + 1):
    if primes[i]:
        for j in range(i*i, root + 1, i):
            primes[j] = False
        x = i*i
        while x <= B:
            if x >= A:
                almost_prime += 1
            x *= i

print(almost_prime)

사실 "제곱"인 수만 구하는 줄 알고 맞왜틀?만 반복했다^^; 다시보니 첫줄에서부터 N제곱(N >= 2)이라 되어있더라. 문제를 잘 읽자...