에라토스테네스의 체1 [JAVA] 소수 찾기 - 에라토스테네스의 체 문제에 대해서는 여기를 클릭하여 가면 된다. 이번에 프로그래머스를 풀면서 에라토스테네스의 체를 사용하여 이 알고리즘을 설명하는 김에 문제풀이도 같이하려 가지고 왔다. 일단 에라토스테네스의 체라는 알고리즘부터 알아보자. 에라토스테네스의 체 원리 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므.. 2021. 10. 20. 이전 1 다음
