에라토스테네스의 체 변형 segmented sieve 배우기

https://deepdata.tistory.com/393

소수를 빠르게 구하는 에라토스테네스의 체 알고리즘

 

 

 

에라토스테네스의 체의 문제는 수행하는 연산의 수가 아니라 메모리 요구량에 있다.

 

n이 매우 큰 경우, 소수의 범위가 메모리에 모두 담기지 않을 수 있다.

 

더 나쁜 것은, n이 그리 크지 않은 경우에도 캐시 사용이 매우 비효율적이라는 점이다.

 

이 알고리즘은 배열 A 전체를 순차적으로 탐색하며, 참조 지역성이 거의 없다.

 

이러한 문제에 대한 해결책으로 분할 체(segmented sieve)가 제안되었는데,

 

이 방법은 범위를 여러 부분으로 나누어 한 번에 일부 구간만 체로 거르는 방식이다.

 

 

 

 

Δ를 √n으로 선택하면, 알고리즘의 공간 복잡도는 O(√n)이 되며, 시간 복잡도는 일반적인 체와 동일하다.

 

------------------------------------------------------------------------------------------------------------------------------------------------------

 

체를 거르는 데는 루트 n까지의 소수들만 있으면 충분하며, 전체 범위를 여러 블록으로 나누어 각 블록을 개별적으로 체로 거르면 됩니다.

 

 

 

 

---------------------------------------------------------------------------------------------------------------------------------------------------------

 

에라토스테네스의 체에서, n의 제곱근을 넘지 않는 소수들의 배수로만 찾으면 된다는 것을 알고 있다.

 

for i in range(1,n+1):
    
    if prime[i] == 1:
        
        for j in range(i*i,n+1,i):
            
            prime[j] = 0

 

 

이렇게 하는 것보다, 

 

for i in range(1,int(n**(1/2))+1):
    
    if prime[i] == 1:
        
        for j in range(i*i,n+1,i):
            
            prime[j] = 0

 

 

이렇게 하면, 시간복잡도는 동일한데 연산의 수가 상당히 줄어든다고 함

 

이거와 비슷한 원리로 매우 큰 n이 주어질때, n의 제곱근들의 배수를 걸러내서 소수를 찾는다는 것이 세그먼트 체의 핵심 원리

 

이렇게 1부터 n까지 배열을 길이가 $\sqrt{n}$인 구간들로 나눈다

 

 

 

1) 첫 구간을 이미 알고 있는 기본 에라토스테네스의 체로 나눈다.

 

2) 각 구간 [low,high]에 대하여, 처음에 1번 구간에서 찾은 소수들을 이용해 이 소수들의 배수를 지우면 된다.

 

3) [low,high] 구간의 길이는 $O(\sqrt{n})$이므로, 공간복잡도가 $O(\sqrt{n})$이다.

 

4) 한번의 반복으로 [low,high] 구간의 소수들을 찾을 수 있다.

 

5) 이제 이거를 여러번 반복하면 1~n구간의 소수들을 찾을 수 있다.

 

전체 시간복잡도는 원래 에라토스테네스의 체와 동일하지만, 공간복잡도를 O(N)에서 $O(\sqrt{n})$으로 줄이게 된다.

 

------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

1. n이하의 소수를 모두 찾는 segment sieve

 

15965번: K번째 소수

 

def simple_sieve(n):
    
    result = [1]*(n+1)
    result[0] = 0
    result[1] = 0

    for i in range(2,int(n**(1/2))+1):
        
        if result[i] == 1:
            
            for j in range(i*i,n+1,i):
                
                result[j] = 0
    
    return [i for i in range(2,n+1) if result[i] == 1]

def segment_sieve(n,x):
    
    length = int(n**(1/2))

    prime = simple_sieve(length)

    total = [0]

    for p in prime:
        
        total.append(p)
    
    if n % length == 0:
        
        m = n//length
    
    else:
        
        m = n//length+1

    for k in range(1,m):

        low = k*length+1
        high = min((k+1)*length,n)

        segment = [1]*(high-low+1)

        for p in prime:

            if low % p == 0:

                i = low//p

            else:

                i = low//p+1
            
            i = i*p

            for j in range(i,high+1,p):
                
                segment[j-low] = 0
        
        for j in range(high-low+1):
            
            if segment[j] == 1:
                
                total.append(j+low)

    return total[x]

k = int(input())

print(segment_sieve(8000000,k))

 

 

기본 에라토스테네스의 체를 이용해서, $\sqrt{n}$ 이하의 소수를 모두 찾는다.

 

def simple_sieve(n):
    
    result = [1]*(n+1)
    result[0] = 0
    result[1] = 0

    for i in range(2,int(n**(1/2))+1):
        
        if result[i] == 1:
            
            for j in range(i*i,n+1,i):
                
                result[j] = 0
    
    return [i for i in range(2,n+1) if result[i] == 1]
    
def segment_sieve(n,x):
    
    length = int(n**(1/2))

    prime = simple_sieve(length)

    total = [0]

    for p in prime:
        
        total.append(p)

 

 

이제 각 구간의 길이를 length로 잡으면, 전체 구간의 개수는 n/length개

 

첫번째 구간 번호를 0이라 하면, k = 0,1,2,...,n/length-1

 

문제는 모든 구간이 정확히 $\sqrt{n}$으로 안나눠질수도 있다는 점

 

예를 들어 1부터 200까지를 보면

 

1 14

15 28

29 42

43 56

57 70

71 84

85 98

99 112

113 126

127 140

141 154

155 168

169 182

183 196

197 200

 

이렇게 마지막 구간이 [197,200]으로 나머지 구간과는 길이가 다르다

 

200을 구간의 길이 length로 나눠서, 나누어 떨어지면 n//length개 있지만..

 

나누어 떨어지지 않으면 n//length+1개가 있다.

 

200을 14로 나누면 14.2857...

 

14개의 길이가 14인 구간이 있고... 나머지 0.2857... 이 부분이 [197,200]을 나타낸다.

 

그래서 각 구간의 번호를 k = 0,1,2,...,ceil(n/length)-1이라고 하면

 

[low,high] = [k*length,(k+1)*length]가 된다.

 

k = 0은 이미 찾았으니까, k = 1부터 순회하면 된다.

 

여기서 high가 n보다 커질수 있으므로, high = min((k+1)*length,n)으로 해주자.

 

이러면 구간의 길이는 length가 아니라 high-low+1로 해줘야한다.

 

    if n % length == 0:
        
        m = n//length
    
    else:
        
        m = n//length+1

    for k in range(1,m):

        low = k*length+1
        high = min((k+1)*length,n)

        segment = [1]*(high-low+1)

 

 

이제 첫 구간에서 구한 소수들 prime에서 순회하여 그 소수를 p라고 하면,

 

[low,high]에 속한 p의 배수들을 모두 찾아 지우면 된다.

 

마찬가지로 ceil(low/p)이 [low,high]에 속한 p의 배수중 가장 작은 수의 인덱스이므로, 이걸 먼저 i로 찾고

 

i에 p를 곱한 다음, high까지 p씩 더해가며 지운다.

 

segment는 0부터 high-low까지 시작하는 배열이지만 i는 low가 더해진 값이라는 것에 주의해서 low만큼 shift해줘야한다.

 

        for p in prime:

            if low % p == 0:

                i = low//p

            else:

                i = low//p+1
            
            i = i*p

            for j in range(i,high+1,p):
                
                segment[j-low] = 0
        
        for j in range(high-low+1):
            
            if segment[j] == 1:
                
                total.append(j+low)

 

 

segment에서 p의 배수들을 모두 지우면, 다시 segment를 순회해서, 지워지지 않은 값들을 찾는다.

 

역시 low만큼 왼쪽으로 shift되어있으므로, j번 인덱스가 지워지지 않은 것이라면, j+low가 소수이다.

 

문제를 풀기 위해 segment에서 찾은 소수들을 모두 total에 넣어서 찾았지만, 

 

어쨌든 n이 매우 크면 total에 담을 수 없다.

 

그래서 total에 담지 않고 print한다면 "이론상" n이 매우 크더라도 모든 소수를 표시할 수는 있다..

 

당연히 n이 매우 크면 문제는 시간 안에는 못돌린다는 뜻

 

하지만 공간복잡도를 $O(\sqrt{n})$으로 줄였기 때문에, 일반적인 체는 메모리에 담을수가 없는데

 

얘는 조금 더 큰 n에 대해서는 시도해볼수는 있다는거지

 

def simple_sieve(n):
    
    result = [1]*(n+1)
    result[0] = 0
    result[1] = 0

    for i in range(2,int(n**(1/2))+1):
        
        if result[i] == 1:
            
            for j in range(i*i,n+1,i):
                
                result[j] = 0
    
    return [i for i in range(2,n+1) if result[i] == 1]

def segment_sieve(n,x):
    
    length = int(n**(1/2))

    prime = simple_sieve(length)

    for p in prime:
        
        print(p,end=' ')
    
    if n % length == 0:
        
        m = n//length
    
    else:
        
        m = n//length+1

    for k in range(1,m):

        low = k*length+1
        high = min((k+1)*length,n)

        segment = [1]*(high-low+1)

        for p in prime:

            if low % p == 0:

                i = low//p

            else:

                i = low//p+1
            
            i = i*p

            for j in range(i,high+1,p):
                
                segment[j-low] = 0
        
        for j in range(high-low+1):
            
            if segment[j] == 1:
                
                print(j+low,end=' ')

 

 

2. 구간 [L,R]에 있는 소수를 찾는 방법

 

특별히 구간 [L,R]에 있는 소수를 찾아야하는 경우가 있다

 

1부터 $\sqrt{R}$까지의 소수를 일반 에라토스테네스의 체로 먼저 찾고,

 

이 소수들의 배수가 구간 [L,R]에 속하는 경우, 지우면 된다.

 

그리고 지워지지 않은 수가 [L,R]에 속하는 소수이다.

 

위의 segment sieve에서 구간을 $\sqrt{n}$으로 나눠서 반복하지 말고,

 

그냥 [L,R]에 대해서 1번만 하면 된다.

 

1929번: 소수 구하기

 

def simple_sieve(n):
    
    result = [1]*(n+1)
    result[0] = 0
    result[1] = 0

    for i in range(2,int(n**(1/2))+1):
        
        if result[i] == 1:
            
            for j in range(i*i,n+1,i):
                
                result[j] = 0
    
    return [i for i in range(2,n+1) if result[i] == 1]

def segment_sieve(m,n):
    
    prime = simple_sieve(int(n**(1/2)))

    segment = [1]*(n-m+1)

    for p in prime:
        
        if m % p == 0:
            
            i = m//p
        
        else:
            
            i = m//p+1
        
        i = i*p

        if i == p:
            
            i += p

        for j in range(i,n+1,p):

            segment[j-m] = 0
    
    if m == 1:
        
        segment[0] = 0
        
    for j in range(n-m+1):
        
        if segment[j] == 1:
            
            print(j+m)

m,n = map(int,input().split())

segment_sieve(m,n)

 

 

이 경우에는 주의할 점이 있는데, 

 

첫번째로 일반 체로 구한 prime에서 순회하여 p에 대해 p의 배수중 [L,R]에 속한 수를 찾아야하는데 

 

1) 문제는 p가 [L,R]에 속할수도 있다는 점이다.

 

그걸 위해 i == p인 경우 i+= p로 스킵하도록 했다.

 

    for p in prime:
        
        if m % p == 0:
            
            i = m//p
        
        else:
            
            i = m//p+1
        
        i = i*p

        if i == p:
            
            i += p

        for j in range(i,n+1,p):

            segment[j-m] = 0

 

 

2) 다음으로 L = 1인 경우 segment에서 지워지지 않는다

 

그래서 L = 1인 경우 segment[0] = 0으로 지워주자.

 

        for j in range(i,n+1,p):

            segment[j-m] = 0
    
    if m == 1:
        
        segment[0] = 0
        
    for j in range(n-m+1):
        
        if segment[j] == 1:
            
            print(j+m)

 

 

이렇게 해서, 딱 1번만 지우고 segment를 순회해서 j+m을 찾으면 된다.