1.1 소수

1.1.1 소수 판별

1.1.1.1 나눠보기 $O(N^{1/2})$

1~ $\rm \sqrt{N}$까지의 수를 나눠봤을 때 나머지가 0인 수가 없으면 소수이다.

1.1.1.2

1.1.2 소수 탐색

1.1.2.1 에라토스테네스의 체 $O(N \log(\log N))$

이전에 나왔던 소수로 나눌 수 없는 수는 소수이다.

1~ $\rm \sqrt{N}$까지의 수를 순회하며, 이전에 나왔던 소수의 배수를 모두 지운다.

1.1.2.2 오일러의 체 $O(N)$

1.2 공약수

1.3