(백준 알고리즘 문제풀이) 1456번 거의 소수

문제

문제 링크

 

문제 접근

• 에라토스테네스의 체 알고리즘 사용
• 에라토스테네스 위키피디아

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

코드

import sys
input = sys.stdin.readline


a, b = map(int, input().split())
result = 0
array = [True for _ in range(int(pow(b, 0.5)) + 1)]

# 에라토스테네스의 체 (10 ** 7까지 리스트 적용)
for i in range(2, int(pow(b, 0.5)) + 1):
    if array[i]:
        j = 2
        while i * j <= int(pow(b, 0.5)):
            array[i * j] = False
            j += 1

for i in range(2, int(pow(b, 0.5))+1):
	# 소수일 경우에 count제곱해준 값이 범위 내에 있을 경우
	if array[i]:
        count = 1
        while True:
            count += 1
            if a <= pow(i, count) <= b:
                result += 1
            if pow(i, count) > b:
                break

print(result)

 

이번 문제는 난이도가 높았다고 생각한다. 처음들어보는 알고리즘이라 그런가 시간이 오래걸린 편이었다. 에라토스테네스의 체 알고리즘의 시간복잡도는 O(NloglogN)으로 시간 초과를 막을 수 있었다.