[알고리즘] 에라토스테네스의 체

1. 에라토스테네스의 체

• 소수(Prime Number) 판별 알고리즘으로 소수란 '양의 약수를 두 개만 가지는 자연수'를 의미하며 2,3,5,7,11, ... 등이 존재합니다. 이러한 소수를 대량으로 빠르고 정확하게 구하는 방법이다.
• 특히, 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘으로 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

동작 과정
1. 2부터 N까지의 모든 자연수를 나열
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다
3. 남은 수 중에서 i의 배수를 모두 제거(i는 제거하지 않는다)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다

2023. 07. 19. 오늘의 문제풀이 ✍

BOJ 1456 - 거의 소수

import sys
import math

input = sys.stdin.readline

a,b = map(int,input().split())
A = [0] * (10**7 + 1)

for i in range(2, len(A)):
    A[i] = i

for i in range(2, int(math.sqrt(len(A)) + 1)):
    if A[i] == 0:
        continue
    for j in range(i * 2, len(A), i):
        A[j] = 0
        
result = 0

for i in range(2, 10**7 + 1):
    if A[i] != 0:
        temp = A[i]
        while A[i] <= b / temp:
            if A[i] >= a / temp:
                result += 1
            temp *= A[i]
            
print(result)