[ BOJ ] 1456 : 거의 소수 ( GOLD 5 ) / Python

문제 링크 : https://www.acmicpc.net/problem/1456

1456번: 거의 소수

문제

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

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

입력

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

출력

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

풀이 과정

10^14 까지의 소수를 전부 구하려면 힘들 것이다...

다행히 우리가 구해야 하는건 어떤 소수의 N제곱이므로, 10^7 까지의 소수만 구해도 된다. 

( 10^7 보다 큰 소수는 2제곱 했을 때 10^14를 초과한다. )

 

10^7 까지의 소수를 구한 뒤, 한 소수마다 B를 넘지 않을 때 까지 계속 제곱시키면서 A보다 크거나 같고 B보다 작거나 같은 거의 소수의 개수를 카운트 한다.

 

import sys
import math
input = sys.stdin.readline

a, b = map(int, input().rstrip().split())

arr = [1 for _ in range(10000001)]
arr[0] = 0
arr[1] = 0
for i in range(2, 10000001):
    for j in range(i**2, 10000001, i):
        arr[j] = 0

cnt = 0
for i in range(2, 10000001):
    if arr[i] == 1:
        now = i**2
        while now <= b:
            if a <= now: cnt += 1
            now *= i
    
print(cnt)