[백준] 1929번 : 소수 구하기, 에라토스테네스의 체 (Kotlin)
에라토스테네스의 체 에라토스테네스의 체는 2~N의 수 중 소수를 판별하는 알고리즘입니다. 해당 알고리즘의 정의를 요약하자면 2부터 N까지의 수 중 2의 배수, 3의 배수, 4의 배수 ... 제곱근N의 배수까지 나눠서 걸러지지 않고 남아 있는 수들이 모두 소수가 된다는 내용입니다. 기존의 소수를 구하는 방식인 소수는 1과 자기 자신만을 약수로 가진다는 조건에 따라 범위 내의 모든 수를 판별하는 방식보다 훨씬 실행속도가 빠르다는 장점이 있습니다. ☞ 예를 들어, 2부터 16까지의 수 중 소수를 찾아보겠습니다. 16의 제곱근은 4이므로 2부터 4까지의 배수를 검사합니다. 2의 배수인 4, 6, 8, 10, 12, 14, 16 / 3의 배수인 6, 9, 12, 15 / 4의 배수인 8, 12, 16 가 모두 걸..
2023. 1. 27.