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

1️⃣문제 설명

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

2️⃣입력

첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.

3️⃣출력

첫째 줄에 총 몇 개가 있는지 출력한다.

 

---

👩🏻‍💻작성한 코드

import math

minV, maxV = map(int, input().split())	# 왼쪽 범위, 오른쪽 범위
prime = [True] * (int(maxV ** 0.5) + 1) # 소수 판별 여부 저장
prime[1] = False
cnt = 0

for i in range(2, int(maxV ** 0.5) + 1):
    if prime[i]:
        if i * i > int(maxV ** 0.5):
            break
        # 에라토스테네스의 체
        for j in range(i ** 2, int(maxV ** 0.5) + 1, i):
            prime[j] = False


for i in range(1, len(prime)):
    if prime[i]:
        temp = i * i
        while True:
            if temp < minV:
                temp *= i
                continue
            if temp > maxV:
                break
            cnt += 1
            temp *= i

print(cnt)

💡코드 설명

prime 리스트는 우선 처음에는 모든 수를 소수라고 가정하고 True 로 초기화 해준 다음, prime[1]일 때의 값은 따로 False임을 저장해준다.

 

그리고 # 에라토스테네스의 체 주석 밑에 작성된 for문을 통해 prime에 저장된 소수의 배수들의 값을 False로 저장해서 소수들만 True 상태로 남겨지게 한다.

 

마지막 for문에서 만약 i가 소수라면, temp에 i의 제곱을 저장하고 주어진 범위 내에 존재하는 소수의 N제곱의 개수를 while문을 통해 카운트하게 된다.