[알고리즘] 백준 1456 파이썬 - 거의 소수

 

1456번: 거의 소수

 

문제

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

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

 

 

문제풀이

import sys
input = sys.stdin.readline
#01
a,b=map(int,input().split())
arr=[False,False]+([True]*(int(b**0.5)-1))
#02
for i in range(2,int(b**0.5)+1):
    if arr[i]:
        if i*i>int(b**0.5):
            break
        for j in range(2*i,int(b**0.5)+1,i):
            arr[j]=False
cnt=0
#03
for i in range(2,len(arr)):
    if arr[i]:
        x=i*i
        while True:
            if x<a:
                x*=i
                continue
            if x>b:
                break
            cnt+=1
            x*=i
print(cnt)

- #01 : 기존 에라토스테네스 보다 타이트하게 리스트를 b의 제곱근까지만 만든다.

- #02 : 이에 맞게 for문도 i*i가 b의 제곱근 보다 크면 바로 아래 for문으로 가지 않고

           break 되게 설계하였다. 그 이유는 문제에서 주어진 값의 범위가 너무 크기에

           모든 값을 연산하면 메모리 초과로 문제를 풀 수 없기 때문이다.

- #03 : arr[i]값이 소수이면 x의 n제곱값이 범위 안에 몇개나 있는지 while문을 통해

           개수를 추가해주고, 만약 i의 제곱값이 b(범위)보다 크면 while문을 종료한다.