koltin
-
[백준][Kotlin] 1456번 거의 소수백준 2023. 3. 22. 18:09
해당 문제는에라토스테네스의 체 원리를 응용하여 작성할 수 있습니다. 에라토스테네스의 체를 간단히 설명하자면 예를 들어 0~30까지 숫자 중 소수를 찾고 싶다면 31개의 1차원 배열을 생성 후 2 부터 시작하여 그 수의 배수들을 모두 소수가 아닌 수 처리를 하여 소수를 찾아내는 기법입니다. 아래 그림은 이해하기 쉽도록 1~30으로 표현하였습니다. 1(소수x) 2(시작) 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1(소수x) 2(시작) 3 5 7 9 11 13 15 17 19 21 23 25 27 29 1(소수x) 2 3(시작) 5 7 11 13 17 19 23 25 29 1(소수x) 2 3 5(시작) 7 11 1..