에라토스테네스의 체

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
에라토스테네스의 체

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

.

그림의 경우, 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

같이 보기[편집]