[파이썬 Python] 에라토스테네스의 체(소수 구하기) 개념과 예제 - (백준 1747)
에라토스테네스의 체 알고리즘 에라토스테네스의 체는 소수를 찾는 방법 중 하나입니다. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다. 2 자신을 제외한 2의 배수를 모두 지웁니다. 남아있는 수 가운데 3은 소수이므로 놔두고, 자신을 제외한 3의 배수를 모두 지웁니다. 남아있는 수 가운데 5는 소수이므로 자기 자신을 제외한 5의 배수를 모두 지웁니다. 남아있는 수 가운데 7은 소수이므로 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남게됩니다. Python 3으로 구현 일단 A 리스트를 인덱스와 수가 같도록 [0,0,2,3,4,5,6,7,8,9 ...] 로 초기화 해줍니다. (0,1은 제외) 2부터 2의 배수들을 차례로 0으로 만들어 줍니다. 이 방식을 ..
2022. 10. 10.
