백준 19291 에라토스테네스의 체 🎻 (Sieve of Eratosthenes) - 백준 1929 python 👷♂️ 소수(Prime Number) 판별 알고리즘이다. 소수 ? 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 ex) 11은 약수가 1과 11 뿐이므로 소수가 맞지만, 30은 1,2,3,5,6,10,15,30 이 약수로 1과 자기자신 뿐만아니라 다른 수도 약수로 가지므로 소수가 아니다. 🚧 알고리즘 에라토스테네스의 체 = 소수 아닌 숫자를 걸러주는 체 소수가 아닌 수를 지워나가 소수만을 남게 한다. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소.. 2022. 1. 19. 이전 1 다음 반응형
