[Python/BOJ] 1456. 거의 소수

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

1456번: 거의 소수

문제

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

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

입력

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

출력

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

풀이

Code

import sys
input = sys.stdin.readline

def solution(a, b) :
    # 1. 소수 판별 리스트, 거의 소수 리스트 생성
    end = int(b ** .5)
    decimal, ans = [True] * (end + 1), 0
    decimal[0], decimal[1] = False, False
    # 2.
    for i in range(2, end + 1) :
        # 2-1. 해당 수가 소수일 경우
        if decimal[i] :
            # 2-1-1.
            for j in range(i + i, end + 1, i) :
                # 소수 판별
                if decimal[j] : decimal[j] = False
    # 3.
    for i in range(1, end + 1) :
        n = 2
        if decimal[i] :
            while i ** n <= b :
                if i ** n >= a :
                    ans += 1
                n += 1
    # 4. 결과 출력
    print(ans)

if __name__ == "__main__":
    a, b = map(int, input().split())
    solution(a, b)