[정수론] 합동식의 성질, 에라토스테네스의 체, (확장) 유클리드 호제법
2023. 7. 27. 16:26
합동식의 성질
유클리드 호제법
확장 유클리드 호제법
에라토스테네스의 체
- 수의 범위 N이 있을 때, 한 수를 두 가지 수로 곱하는 쌍의 개수는 $\sqrt{n}$ 이다.
- 즉, 시간복잡도는 $O(\sqrt{N}/\ln{\sqrt{N}})$
'* 언어 | 알고리즘 > 알고리즘 개념' 카테고리의 다른 글
| [트리] 최단경로 찾기 : 플로이드-워셜, 다익스트라, 벨만포드 (0) | 2023.08.03 |
|---|---|
| [트리] LCA, 오일러 투어, 단절점 찾기, (0) | 2023.08.01 |
| [그래프] 서로소 집합 Union-Find, 위상정렬, 최소신장트리 (0) | 2023.07.31 |
| [트리] 펜윅 트리 (0) | 2023.07.27 |
| [트리] 이진 트리, 힙, 세그먼트 트리 (0) | 2023.07.26 |
