소수 판별 (1) 썸네일형 리스트형 오일러의 체(Linear Sieve)로 O(logn) 소인수 분해 하기 이 게시글에서는 linear sieve 또는 오일러의 체라 불리는 알고리즘에 대해 알아보고 그 구현을 배우도록 한다. Linear Sieve Linear sieve는 에라토스테네스의 체를 개선하여 N 이하의 소수를 $O(N)$ 만에 찾고 N 이하 자연수의 소인수 분해를 $O(\log N)$에 할 수 있게 만들어 준다. 과정은 다음과 같다. 소수의 여부 대신 해당 수의 최소 소인수(Smallest Prime Factor. 이하 spf)를 나타내는 체(배열)를 둔다. spf 체를 순회하면서 해당 index의 값이 비어있는(0) 경우 소수가 된다. 그래서 spf[index] = index가 되고 index를 소수 집합에 추가한다. 그런 다음 현재까지 판별한 모든 소수들에 대해 반복문을 돌면서 spf[index.. 이전 1 다음