[python] 백준 1456 거의 소수

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

1456번: 거의 소수

 

문제 해결

• 편하게 0부터 끝 수(b)까지 리스트 만들어 놓고 하면 메모리 초과가 걸린다.
• 따라서 int(sqrt(b))+1 개의 리스트 공간을 만들어 놓고 소수인 인덱스를 제곱, 세제곱 하면서 a와 b 사이에 들어오는지를 확인해야 할 것이다.

CODE

import math
import sys
input = sys.stdin.readline
a, b = map(int, input().split())
A = [0]*(int(math.sqrt(b))+1)
A[2] = 2
for i in range(3,len(A),2):
    A[i] = i

for i in range(3, int(math.sqrt(b))+1,2):
    if A[i] ==0: continue
    for j in range(i+i, int(math.sqrt(b))+1,i):
        A[j] = 0
count = 0

for i in range(2,int(math.sqrt(b))+1):
    if A[i] !=0:
        temp = A[i]
        while A[i] <= b/temp :
            if A[i] >= a/temp:
                count += 1
            temp = temp*A[i]
print(count)