에스토라네스의 체(소수 쉽게 구하기)
2019. 1. 5. 03:35ㆍAlgorithm
에스토라네스의 체
에스토라네스의 체는 소수의 배수들을 모두 지움으로써 소수를 구할 수 있는 알고리즘이다. 그렇게 어렵지 않으니 코드로 설명하겠습니다.
백준 1929번을 통해 코드를 만들어 보겠다.
코드를 보면 2부터 입력값의 제곱근 까지 나누어서 나머지가 0이되면 소수가 아니게 된다. 만약에 2를 넣었는데 2의 제곱근은 1.414정도 임으로 반복문이 돌지 않고 소수로 판단하여 출력하게 됩니다. 그리고 만약에 9가 들어가게 된다면 9의 제곱근은 3이기 때문에 3으로 나누어져 나머지가 0임으로 결국 소수가 아니라고 판단하게 됩니다.
'Algorithm' 카테고리의 다른 글
| 백준 1011 Fly me to the Alpha Centauri (0) | 2020.11.18 |
|---|---|
| knapsack 문제 (0) | 2019.06.11 |