에라토스테네스의 체1

• 

  에라토스테네스의 체 (+Java 코드) 1. 에라토스테네스의 체란? 에라토스테네스의 체란 소수를 찾는 방법입니다. 해당 방법은 마치 체로 치듯이 수를 걸러낸다고 해서 에라토스테네스의 체 라고 부른다고 합니다. 2. 동작 방식 우리는 체에 집중해서 하나씩 소수가 아닌 수를 걸러낼 것 입니다. 즉, "소수를 찾고 해당 소수의 배수를 모두 지우면 소수만 남는다!" 입니다. 예를 들어, 100 이하의 자연수 중 소수를 모두 찾아보도록 하겠습니다. (1) 1 제거 우선 소수도, 합성수도 아닌 유일한 자연수인 1을 제거합니다. (2) 2를 제외한 2의 배수 제거 다음으로는 2를 제외한 2의 배수를 제거합니다. 무언가의 배수라는 것은 소수가 아니라는 것을 뜻하니까요! (3) 3을 제외한 3의 배수 제거 다음은 3을 제외한 3의 배수를 제거합니다. (4) .. Algorithm & Data Structure/이론 2021. 7. 27.