Coding Memo

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

소수 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 쉬운 문제지만 소수를 찾는 방법을 이용하였기 때문에 포스팅한다. 문제 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이..