[백준] 1456번 : 거의 소수 - [Python/파이썬]

문제

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

1456번: 거의 소수

 

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

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

입력

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

출력

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

코드

import sys
import math

a, b= map(int, sys.stdin.readline().split())
c=int(math.sqrt(b))+1

x=[True]*(c)
x[1]=False
for i in range(2,c):
    if x[i]:
        if i**2 >c: break
        for j in range(i*i, c, i):
            x[j]=False

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

print(count)

문제 해결

에라토스테네스의 체를 활용하는 문제이다. 

일일히 소수인지 파악해버리면 시간복잡도가 엄청 높게 나오기 때문에 주의해서 코드를 작성해야한다,