CS ﹒ Algorithm/Algorithm
2022. 6. 24.
0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체
고대 그리스 수학자 에라토스테네스가 발견한 소수를 구하는 간편한 방법이다. 알고리즘 중에 그나마 쉬운 편에 속한다. (1) 우선 0과 1은 소수가 아니기때문에 제외한다. (2) 소수인 2를 제외한 2의 배수를 모두 제외한다. (3) 소수인 3을 제외한 3의 배수를 모두 제외한다. (4) 소수인 5를 제외한 5의 배수를 모두 제외한다. (5) 소수인 7을 제외한 7의 배수를 모두 제외한다. (6) 위의 과정을 반복하며 제외되지 않은 소수 n을 제외한 n의 배수를 제외.. 무한 반복 글로만 읽어도 그럭저럭 이해가 되겠지만 아래의 친절한 그림을 보고나면 더욱 와닿을 것이다. 이 알고리즘을 JAVA로 작성해보자. public static String test(int num) { // 인자로 제공되는 수와 인덱..