Coding Memo

이 글은 `알고리즘 문제해결전략 - 구종만 (인사이트)의 내용을 일부 참고하여 작성하였습니다. 에라토스테네스의 체를 이용한 소수 찾기 기법은 2 부터 시작해 해당 값이 소수이면, 그 값의 배수를 숫자가 있는 풀(pool)에서 지워나가는 방법을 이용해 풀에 소수만 남기는 기법이다. 어떤 소수인 n에 대해서 n * i (i > 0)에 해당하는 값을 걸러내는 체를 이용한다. 위 방법에서 체에 대한 배열의 크기는 확인하려는 값의 최댓값이 될 것이다. 만약 1억까지의 수를 확인하려고 하면 boolean 타입의 배열을 써도 1억 바이트나 사용해야 한다는 것이다. 사실 0과 1만을 표현하는데 있어서 가장 좋은 데이터는 비트이다. 하지만 보통 프로그램 언어에서는 true/false를 표현하는데 사용되는 boolean ..