소수는 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어 떨어지지 않는 자연수 입니다.
예를 들면 2, 3, 5, 7 등 다른 수로 나누어 질 수 없는 수입니다.
에라토스테네스의 체
소수를 구하는 대표적인 판별법은 에라토스테네스의 체가 있습니다.
에라토스테네스의 체를 이용해 소수를 구하는 방법은 다음과 같습니다.
- 구하고자하는 소수의 범위 만큼 1차원 배열 생성
- 2부터 시작하여 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지움
- 다음 숫자 중 지워지지 않은 숫자로 이동
- 배열의 끝에 도달할 때까지 2~3번 반복
에라토스테네스의 체의 경우 이중 for문을 이용하지만 배수를 삭제하는 연산으로 인해 실제 구현에서 for문이 생략되는 경우가 빈번하게 발생합니다. 그렇기 때문에 O(nlog(logn))의 시간 복잡도가 나옵니다.
'Algorithm > 이론' 카테고리의 다른 글
유니온 파인드 (Union-Find) (0) | 2023.05.19 |
---|---|
유클리드 호제법 (0) | 2023.05.19 |
그리디 알고리즘 (Greedy) - JAVA (0) | 2023.05.19 |
이진 탐색 (Binary Search) - JAVA (0) | 2023.05.18 |
넓이 우선 탐색 (BFS : Breadth Frist Search) - JAVA (0) | 2023.05.18 |