1456. 거의 소수: 에라토스테네스의 체(Seive of Eratosthenes)

1456. 거의 소수

문제

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.
두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

제한

1 ≤ A ≤ B ≤ 1014

 

에라토스테네스의 체

• 정수론: 소수
• 에라토스테네스의 체는 범위 내에 있는 소수를 구하는 알고리즘으로, O(N)의 시간복잡도를 가진, 소수를 구하는 방법 중 가장 빠른 알고리즘이다. 당신이 이걸 고안해내지 않는 바에야 모르면 못 푼다. 못할 건 없겠지만 시간 낭비다.
• 어떤 한 수가 소수인지 아닌지 판단하는 소수 판별법과는 다르므로 하나의 수가 소수인지 판단하는 것은 나중에 살펴보자.

에라토스테네스의 체: 작동 방식은 이걸 보면 직관적으로 알 수 있다. 120 까지의 소수를 구하는 과정 (from wikipedia, [에라토스테네스의 체])

 

설명

1. 소수도, 합성수도 아닌 유일한 자연수 1을 제외한다.
2. 2를 제외한 2의 배수를 제거한다.
3. 3을 제외한 3의 배수를 제거한다.
4. 4의 배수는 지울 필요 없으며(이미 지워짐), 5를 제외한 5의 배수를 제거한다.
5. 7을 제외한 7의 배수를 제거한다.
6. 그 다음 남아있는 11의 경우 11의 제곱이 121으로, 120을 넘어가므로 더 이상 제거할 필요가 없다.

❓ Q: 왜 11의 제곱부터 따지는지?
A: 11 X 2, 11 X 3, … 11 X 10 은 이미 이전의 시행에서 모조리 다 지워졌기 때문에 남아있는 수들은 모두 소수이다.

• 그림에서 보듯이 체로 치는 것 같은 방법이고 발견한 고대 그리스 수학자인 에라토스테네스의 이름을 따서 “에라토스테네스의 체” 라고 부른다.
• 수학 쪽으로 관심이 있다면: 모듈러 & 소수 정리를 찾아 보면 될 것 같다.

 

소스 코드

def eratosthenes(n):
        multiples = set()
        primes = []
        for i in range(2, n+1):
                if i not in multiples:
                        primes.append(i)
                        multiples.update(range(i*i, n+1, i)) # i*i부터 i씩 커지며 지워간다.
        return primes

print(eratosthenes(30)) # 30 까지의 소수를 구하여 출력한다.

이 코드는 에라토스테네스의 체 알고리즘을 통해 소수를 구해본 것 뿐이다. 문제 풀이에서는 이렇게 비효율적인 코드는 사용하지 않는다.

 

풀이

import sys
input = sys.stdin.readline

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

def eratosthenes(n):
    if n == 1:
        return []
    multiples = set()
    primes = []
    nearprimes = []
    for i in range(2, n+1):
        if i not in multiples:
            primes.append(i)

            a = i*i
            while a < n:
                nearprimes.append(a)
                a *= i

            multiples.update(range(i*i, n+1, i))
    return nearprimes

print(len(eratosthenes(B)) - len(eratosthenes(A)))

⇒ 하하 그렇게 모조리 다 계산하면 메모리 초과가 뜬답니다.

 

개선

By Bing AI, generated in 2023/06/29
에라토스테네스의 체 알고리즘을 최적화하는 방법으로는 다음과 같은 것들이 있습니다.

1. 홀수만 검사하기: 2를 제외한 모든 짝수는 소수가 아니므로, 3부터 시작하여 홀수만 검사하는 것으로 계산량을 줄일 수 있습니다.
2. 제곱근까지만 검사하기: 어떤 수의 약수는 그 수의 제곱근보다 작거나 같은 수 중에서 찾을 수 있습니다. 따라서 에라토스테네스의 체 알고리즘에서도 찾고자 하는 범위의 제곱근까지만 검사하면 됩니다.
3. 비트맵 사용하기: 에라토스테네스의 체 알고리즘에서는 각 수가 소수인지 아닌지를 저장해야 합니다. 이때 비트맵을 사용하면 메모리 사용량을 줄일 수 있습니다.

(1) 에라토스테네스의 체

(2) 최적화된 에라토스테네스의 체

• (2)번 글에 설명되어 있듯이, 주어진 A 까지의 소수를 구할 경우, A의 제곱근까지만 확인해 보면 된다: 합성수 K가 p*q 라고 할 때 하나는 sqrt(K) 이하, 하나는 sqrt(K) 이상일 것이기 때문이다.
• 연산하여 메모리 사용을 늘리는 대신 비트맵을 사용해 과부하를 줄일 수 있다.
• 위에서 설명한 코드는 에라토스테네스의 체를 이용해 리스트를 뽑아내는 매우 기본적인 코드이다.
• 에라토스테네스의 체 알고리즘은 메모리를 많이 차지하기 때문에 코드에서 조금이라도 메모리 사용이 높으면 메모리 초과가 발생한다.
• + 비트 마스크를 사용해 풀 수 있는 방법이 있다. 이 경우는 매우 어려운 문제가 아니라면 사용할 필요는 없다: 구상이 어려움, 코드가 길어 시간 부족할 수 있음: (3) 비트마스크를 이용한 에라토스테네스의 체

import sys
input = sys.stdin.readline

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

sqrtB = int(B ** 0.5)
primes = [True] * (sqrtB + 1)
primes[1] = False

for i in range(2, sqrtB + 1):
    if primes[i]:
        if (i * i) > sqrtB:
            break
        for j in range(i*i, sqrtB+1, i):
            primes[j] = False

cnt = 0
for i in range(1, len(primes)):
    if primes[i]:
        res = i * i
        while True:
            if res < A:
                res *= i
                continue
            if res > B:
                break
            res *= i
            cnt += 1

print(cnt)

풀이들이 정형화 되어있지는 않고, 위 셋 중 2번, 3번 방법을 참고하여 최적화한 코드들이 대부분. 그 중 한 가지를 참고하여 작성한 코드이다. 이 외에도 여러 코드들이 있는데 여러 코드들을 살펴보는 것도 사람들이 어떻게 생각하는지 엿볼 수 있는 기회인 듯.

 

풀이 예시 1

N = 10**7+5
sieve = [True]*(N+100)
sieve[0] = False
sieve[1] = False
sieve[2] = True
prime = 2

while prime**prime <= N:
        if not sieve[prime]:
                prime += 1
                continue
        for t in range(2*prime, N+3, prime): sieve[t] = False
        prime += 1

A,B=map(int, input().split())
cnt = 0
for p in range(2,N):
        if not sieve[p]: continue
        mul = p*p
        while mul <= B:
                cnt += (A <= mul)
                mul *= p
print(cnt)

 

풀이 예시 2

import math, sys
input = sys.stdin.readline

a, b = map(int, input().split())
sqrtb = int(math.sqrt(b))
A = [0] * (sqrtb + 1) # 소수가 아니면 0이다
A[2] = 2

for i in range(3, len(A), 2): # 홀수들만 남겨 둠
    A[i] = i

for i in range(3, sqrtb+1, 2): # 홀수들만 확인해 봄
    if A[i] == 0: continue # ? 왜 있지?
    for j in range(i+i, sqrtb+1, i): # 홀수들의 배수들 제거
        A[j] = 0

cnt = 0
for i in range(2, sqrtb+1):
    if A[i] != 0:
        temp = A[i] # 소수 추출
        while A[i] <= b/temp:
            if A[i] >= a/temp:
                cnt += 1
            temp = temp * A[i]
print(cnt)                          # 특이하구먼...