[BaekJoon] 거의 소수 - 1456 (Python3, Gold V)

문제 링크

1456번: 거의 소수

성능 요약

메모리: 111368 KB, 시간: 2920 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

제출 일자

2024년 4월 15일 17:09:48

문제 설명

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

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

입력

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

출력

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

# 에라토스테네스의 체
import sys, math
input = sys.stdin.readline

a, b = map(int, input().split())
prime = [True] * (int(math.sqrt(b))+1)
prime[1] = False

for i in range(2, int(math.sqrt(b))+1):
    if prime[i]:
        if i * i > int(math.sqrt(b)):
            break
        for j in range(i**2, int(math.sqrt(b)) + 1, i):
            prime[j] = False

# for i in range(2, b):
#     if(prime[i]): print(i)
count = 0
for i in range(2, len(prime)):
    if prime[i]:
        res = i * i
        while True:
            if res < a:
                res *= i
                continue
            if res > b:
                break
            res *= i
            count += 1
print(count)

'''
Input
1 1000
Output
25

Input2
1 10
Output2
3

Input3
5324 894739
Output3
183
'''