[백준] 1456번 거의 소수

💡문제접근

• B의 최댓값이 10^14까지 매우 큰 수로 나올 수 있기 때문에 배열로 선언한다면 메모리초과가 발생할 것이다. 따라서 제곱근을 이용해서 절반까지를 배열로 선언해줘야한다.

💡코드(메모리 : 109380KB, 시간 : 3216ms)

import sys
input = sys.stdin.readline

A, B = map(int, input().strip().split())

arr = [True] * (int(B**0.5)+1)
arr[0] = False
arr[1] = False
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(i*i, int(B**0.5)+1, i):
            arr[j] = False

cnt = 0
for i in range(len(arr)):
    if arr[i]:
    	# prime_number : 거의 소수
        prime_number = i * i
        while True:
        	# 만약 N제곱 꼴의 거의 소수가 A, B 사이에 들어가지 못한다면?
            # 멈추는 것이 아니라 계속 제곱을 계산해주어 범위에 들어가게끔 유도한다.
            if prime_number < A:
                prime_number *= i
                continue
            # 만약 N제곱 꼴의 거의 소수가 B보다 크다면?
            if prime_number > B:
                break
            prime_number *= i
            cnt += 1
print(cnt)

💡소요시간 : 17m