🏘️Euler Sieve

intro

🏘️ 소수 판정법으로 유명한 에라토스테네스의 체(Sieve of Eratosthenes)를 개선한 '오일러의 체(Euler Sieve)'에 대해서 소개한다. 에라토스테네스의 체는 소수 판별 시간 복잡도가 O(nloglogn)임이 알려져 있고, 이를 개선한 오일러의 체 시간 복잡도는 단 선형 시간만에 O(n)으로 판별이 가능하다.

 

🏘️ 에라토스테네스의 체의 시간 복잡도가 선형 시간(O(n))이 될 수 없는 이유는 합성수 210을 들면 쉽게 알 수 있다. 210은 2x3x5x7로 나타낼 수 있는데, 에라토스테네스의 체에 의해서는 2x3x5x7 / 2x3x5x7 / 2x3x5x7 / 2x3x5x7 와 같이 각각 빨간색 숫자일 때 210이 합성수임을 중복해서 알려주고 있다.

 

🏘️ 따라서, 이를 단 한번에 합성수가 아님을 알려주기 위해 개선한 알고리즘이 Euler Sieve 알고리즘이고, 시간 복잡도는 O(n). 따라서 에라토스테네스의 체 변형 판 'Linear Sieve'라 부르기도 한다. 오일러의 체를 실행하면 N이하의 수의 ① 각각 자연수의 최소 소인수 list(spf(smallest prime factor) list)와 ② 소수 list를 두 개나 얻을 수 있다. 또한, spf list를 사용해 ③ 빠른 소인수분해도 가능하다.

1. making an Euler Sieve

ex) N = 29 가정

 

① 초기화) 30개의 숫자가 들어갈 수 있는 list를 만든다(index 0부터 시작하므로 30개 준비)

(1) 총 30개의 칸에 0부터 29까지의 숫자를 차례대로 (index 그대로) 집어 넣는다.

 

(2) 2 포함 29까지의 모든 짝수는 2로 바꾼다. (모든 짝수는 무조건 소인수는 2이므로 초기화 때 미리 설정해놓음)

 

☆ 짝수는 전체 범위의 절반이나 해당하므로 미리 2로 바꾸면 탐색 시간 줄일 수 있음

(3) prime list에 2부터 넣고 준비.

 

② x를 3부터 floor(√N)까지 홀수만 돌린다. (돌리는 변수 x 가정) (아래 그림 초록색 숫자)

(배수만큼 O(N) 시간 복잡도로 searching하기 때문에 전체 N까지 돌릴 필요 x / 또한 짝수는 spf 무조건 2이므로 생략. 홀수만 돌림)

 

ex) 즉 x를 3하고 5만 돌린다.

③ sieve[x]가 index 나 자신 x라면 (if sieve[x] == x), x는 x보다 작은 수의 배수에서 걸러지지 않았다는 의미, 즉 x의 약수는 1과 나 자신만 있음이 증명되었기에 소수임이 증명됨. 따라서 prime list에 넣는다

 

④ 그리고 y라는 변수를 x*x부터 sieve 끝까지 x*2 step으로 돌면서 x의 배수(x 자신 제외)인 y는 모두 합성수(소수의 배수는 모두 합성수)이므로 소수가 아니다. 이 때 sieve[y]가 이미 합성수임이 밝혀졌다면(sieve[y] != y) 해당 y는 x가 최소 소인수가 아니므로 pass. sieve[y]가 y로 초기화된 상태로 그대로 있다면 해당 y는 x가 최소 소인수이므로 sieve[y] = x 마킹.

 

☆ x*2가 아니라 x*x부터 도는 이유는, x*x 이하의 x의 배수는 spf를 x로 소인수를 가지지 않기 때문.

 

☆ step을 x가 아니라 x*2로 설정한 이유는, x를 짝수배한 숫자는 무조건 짝수가 소인수로 들어가므로 2가 spf이기 때문.

 

ex) x가 3일 때, 3의 제곱부터 끝까지 6씩 step 돌면서 15, 21, 27에 3 마킹

ex) x가 5일때, 5의 제곱부터 끝까지 10씩 step 돌면서 25에 5 마킹

 

⑤ N까지의 spf list 완성(위 오른쪽 그림). spf list만 원한다면 x의 범위를 √N으로 탐색해도 충분하나, prime list까지 원한다면 N까지 탐색해 sieve[x] == x인 경우 차례대로 prime list에 넣어주면 된다. 그럴 경우 prime list는 [3, 5, 7, 11, 13, 17, 19, 23, 29] 완성

2. Factorization

① 위에서 만든 spf list를 활용해 빠른 소인수분해를 진행할 수 있다. 예를 들어 num이라는 변수의 소인수분해를 진행한다면 num의 spf 값을 체크. 나 자신이라면 num이 소수이므로 num 한 개 출력하면 끝. 그렇지 않다면 num//spf 값의 spf 값을 구해나가면 된다. 따라서 num이 1이 될 때까지 num에 spf를 나누어나가며 factorization을 완성해나가면 된다.

 

ex) num이 210이라면 spf[num](=spf[210])이 2이므로 2 저장한 뒤, 210을 2로 나눈 105를 num으로 설정 spf[num](spf[105])을 보니 3이므로 3 저장한 뒤, 3으로 나눈 35를 num으로 설정. spf[35]는 5이므로 5 저장하고 7을 num으로 설정. spf[7]은 7이므로 7 저장하고 1을 num으로 설정. num이 1이 되었으므로 종료.

 

ex) num = 27일 때 소인수를 찾는 과정을 그림으로 나타내면 아래와 같다.

: 노란색 박스가 27의 소인수로 3, 3, 3임을 바로 알 수 있다.

code

① linear sieve 완성 코드(n까지의 spf list)

#linear sieve
sieve = [i for i in range(n+1)]
sieve[4::2] = [2]*(math.ceil((len(sieve)-4)/2))

for x in range(3,(int(len(sieve)**(1/2)))+1,2):
    if sieve[x] == x:
        for y in range(x*x,len(sieve),x*2):
            if sieve[y] == y:
                sieve[y] = x

 

② factorization 코드(num 소인수분해)

ans=[]
while num > 1:
    ans.append(spf[num])
    num//=spf[num]
print(*ans)

examples

★ <백준 G4 16563 어려운 소인수분해> ★ 문제 링크

Q. 말 그대로 입력한 수들의 소인수분해를 진행해 모든 소인수들을 각각 출력해주는 문제. N의 범위가 5백만까지이므로 euler sieve 활용

 

★ <백준 G2 3142 즐거운 삶을 위한 노력> ★ 문제 링크

Q. 완전제곱수 여부를 소인수 종류별 짝수 개수인지 판단하는 문제. 소인수 종류가 들어간 set() 자료형 만들고 입력한 숫자의 소인수가 set에 없다면 삽입. 있다면 set()에 존재하는 소인수 없애는 방식으로 진행해 set에 남는 소인수 여부에 따라 완전제곱수 판별하는 문제