알고리즘, 자료구조
[정수론] 에라토스테네스의 체 / 배열 구현
에라토스테네스의 체 고대 그리스 수학자인 에라토스테네스가 고안했다. 주어진 자연수보다 작거나 같은 소수들이 어떤 것들이 있는지 찾아내는 알고리즘이다. 주어진 자연수 만큼 표를 그려놓은 뒤, 소수의 배수들을 지워나간다. 최종적으로 남은 숫자들은 소수이다. 자연수 25에 소수가 몇개 포함되어 있는지 에라토스테네스의 체를 이용해 판별해보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 자연수 1은 소수가 아니다. 2는 유일한 짝수인 소수이다. 2는 소수로써 남겨두고 2의 배수들은 전부 지워준다. 3은 소수이다. 3은 소수로써 남겨두고 3의 배수들은 전부 지워준다. 4는 이미 합성수라고 이전에 결론이 났다. 넘어간다. 5는 소수이다. 5는..
