백준 1456번

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

1456번: 거의 소수

import math

a,b =map(int,input().split())
array = [1 for i in range(int(math.sqrt(b)) + 1)] # 처음엔 모든 수가 소수(1)인 것으로 초기화
almost_prime =[]
cnt=0

# 에라토스테네스의 체 알고리즘 
for i in range(2, int(math.sqrt(b)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i] == 1: # i가 소수인 경우 (남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        j = 2 
        while i * j <= int(math.sqrt(b)):
          #소수가 아닌 수 설정
            array[i * j] = 0  
            j += 1

for i in range(2, int(math.sqrt(b)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i] == 1: # i가 소수인 경우 (남은 수인 경우)  
        j = 2 
        # i를 제외한 i의 제곱을 세주기
        while i**j <= b :
            #a이상 일때만 세주기
            if i**j>=a:
                cnt+=1
            j += 1
                                  
print(cnt)

 

거의 소수의 최대 값은 b의 제곱근임,

따라서 에라토스테네스의 체를 사용할 때도 b제곱근 만큼의 공간만 사용 가능

1. 에라토스테네스의 체를 사용하여 소수를 찾음
2. 소수인 경우 거듭 제곱이 a이상 이고 b이하인 경우 세주기