Linear Sieve (2) 썸네일형 리스트형 백준 16563 - 어려운 소인수분해 https://www.acmicpc.net/problem/16563 소인수 분해는 $O(\sqrt N)$의 시간 복잡도로 $\sqrt N$까지 반복문을 돌아 자연수를 나누는 방법이 가장 잘 알려져 있다. 하지만 이 문제는 소인수 분해를 해야 할 수의 개수가 $N \leq 10^{6}$이므로 이 방법을 사용하면 TLE 판정을 받게 된다. Linear sieve를 이용하여 소인수 분해를 $O(\log N)$에 할 수 있는 방법이 있다. Linear sieve를 사용하여 소수 목록을 $O(N)$에 구한 후 소인수 분해를 실시하면 1초 이하의 시간으로 AC를 받을 수 있다. Linear sieve를 알지 못한다면 이 글을 참조하여 사용하면 된다. 오일러의 체(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 다음
