Algorithm
에라토스테네스의 체(2022.04.13)
목차 에라토스테네스의 체 소수판정의 가장 기본이 되는 에라토스테네스의 체이다. 소수는 약수가 1과 자기자신만을 가지는 수이다. 소수를 구하는 알고리즘을 찾아보자. 알기 쉽게 예를 들어보겠다. 1~50까지의 소수 1부터 50까지의 수 중 소수를 찾는 방법을 보자 먼저 숫자를 다 적어본다. 그리고, 제일 첫번째 소수인 2의 배수를 다 지워준다. 지워주는 이유를 생각을 해보면, 소수는 1과 자기자신만을 약수로 가지는 수 이다. 어떤 수의 배수는 소수가 될 수 없다. 그러므로 범위내의 소수의 배수를 다 지워주면, 소수만 남게된다. 그렇게 2의 배수를 지우고, 3의 배수 5의 배수 7의 배수 이렇게 까지만 지워주면 나머지 수 들은 전부 소수가 된다. 왜 7까지만 지워줄까? 근데 앞에서 그러므로 범위내의 소수의 배..
