수학1 에라토스테네스의 체(Eratosthenes' sieve) 에라토스테네스의 체(Eratosthenes' sieve) 1부터 N사이의 모든 소수와 소수가 아닌 수를 찾는 방법이다. 소수는 1과 자기 자신만을 약수로 가지는 수이다. 쉽게 말해 소수는 자기 자신과 1로 밖에 못 나누는 수이다. 이러한 원리를 이용해 배수를 지우면서 소수가 아닌 수를 배제해 나가는 방법이다. 즉, 1)--- 2의 배수인 4, 6, 8, 10, 12..........지움 3의 배수이면서 지워지지 않은 수인 9, 15, 21.......지움 . . . . . . 2)--- 이러한 과정을 반복하며 소수가 아닌 수를 지워나간 후 마지막까지 지워지지 않은 수인 소수를 찾는 방법이다. ----- 예를 들어 1 ~ 50 사이의 소수를 찾는 다면, 1은 소수가 아니므로 먼저 배제하고 2의 배수들을 배.. 2019. 3. 17. 이전 1 다음