에라토스테네스의 체

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다.

알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우, $11^2 > 120$이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

에라토스테네스의 체를 프로그래밍 언어로 구현

◆ C++로 이 알고리즘을 다음과 같이 구현할 수 있다.

void Eratos(int n)
{
        // 배열을 동적할당 할 포인터 선언
        bool* PrimeArray;
 
        // 만일 n이 1보다 작거나 같으면 함수 종료
        if(n<=1) return;
 
        /*      2부터 n까지 n-1개를 저장할 수 있는 배열 할당
                배열 참조 번호와 소수와 일치하도록 배열의 크기는
                n+1 길이만큼 할당(인덱스 번호 0과 1은 사용하지 않음) */
        PrimeArray=new bool[n+1];
        /*      배열초기화
                처음엔 모두 소수로 보고 true값을 줌        */
        for(int i=2; i<=n; i++) PrimeArray[i]=true;
        /*      에라토스테네스의 체에 맞게 소수를 구함
                만일, PrimeArray[i]가 true이면 i 이후의 i 배수는
                약수로 i를 가지고 있는 것이 되므로 i 이후의 i 배수에 대해
                false값을 준다.
                PrimeArray[i]가 false이면 i는 이미 소수가 아니므로 i의 배수 역시
                소수가 아니게 된다. 그러므로 검사할 필요도 없다.    */
        for(int i=2; (i*i)<=n; i++)
        {
                if(PrimeArray[i])
                {
                        for(int j=i+i; j<=n; j+=i) PrimeArray[j]=false;
                }
        }
 
        // 이후의 작업 ...
 
}

◆ java 로 구현

public class Eratos {
        public static void main(String[] args) {
                // ArrayList로 구현
                ArrayList<Boolean> primeList;
 
                // 사용자로부터의 콘솔 입력
                Scanner scan = new Scanner(System.in);
                int n = scan.nextInt();
 
                // n <= 1 일 때 종료 
                if(n <= 1) return;
 
                // n+1만큼 할당
                primeList = new ArrayList<Boolean>(n+1);
                // 0번째와 1번째를 소수 아님으로 처리 
                primeList.add(false);
                primeList.add(false);
                // 2~ n 까지 소수로 설정
                for(int i=2; i<=n; i++ )
                        primeList.add(i, true);
 
                // 2 부터  ~ i*i <= n
                // 각각의 배수들을 지워간다.
                for(int i=2; (i*i)<=n; i++){
                        if(primeList.get(i)){
                                for(int j =i+i; j<=n; j+=i) primeList.set(j, false);
                        }
                }
                StringBuffer sb = new StringBuffer();
                sb.append("{");
                for(int i=0; i<=n; i++){
                        if(primeList.get(i) == true){
                                sb.append(i);
                                sb.append(",");
                        }
                }
                sb.setCharAt(sb.length()-1, '}');
 
                String str = new String(sb);
                System.out.println(str);
 
        }
}

◆ Python 으로 구현

    #결과 값을 저장하는 목록을 미리 생성한다.
    result = []
    #전체 범위를 지정한다. : 1은 소수임을 알고 있으므로 제외하고 2부터 수행해야 하지만 초기값은 별도로 생성할 것이므로 3부터 999까지의 범위로 한다.
    candidates = range(3,1000)
    #초기값을 설정한다.
    base = 2
    #초기값의 배수를 구하기 위한 임시 변수를 생성한다.
    product = base
 
#전체 범위 내에서 "에라토스테네스의 체" 알고리즘을 수행한다.
    while candidates:
        #임시변수가 1000미만일 때까지 다음을 수행한다.
        while product < 1000:
            #임시변수가 전체 범위내 존재한다면 :
            if product in candidates:
                #전체 범위 목록에서 임시변수를 삭제한다.
                candidates.remove(product)
            #임시변수는 기본값의 배수이다.
            product = product+base
        #결과 목록에 기본값을 추가한다.
        result.append(base)
        #다음 기본값은 (이미 걸러진)전체 목록의 첫번째 값이다. : 1회 걸렀을 경우 2와 2의 배수를 모두 삭제했으므로 3이다.
        base = candidates[0]
        #초기값의 배수를 구하기 위해 임시 변수를 다시 생성한다.
        product = base
        #전체 범위에서 초기값을 제거한다.
        del candidates[0]
    # 범위 내의 마지막 기본값을 결과 목록에 추가한다.
    result.append(base)
    #결과 목록을 화면에 출력한다.
    print result