[Algorithm] 에라토스테네스의 체 (Swift/C++)

에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다.

마치 체로 치듯이 수를 걸러낸다고 해서 붙여진 이름으로, 주로 대량의 소수를 한 번에 판별할 때 사용한다.

 

알고리즘 구현 순서는 아래와 같다.

 

 

1. 판별할 숫자의 크기만큼 배열을 할당하고, 배열의 인덱스를 해당 배열 요소의 값으로 저장한다.

2. 숫자 2부터 시작해서 차례대로 2의 배수에 해당하는 숫자를 인덱스로 가진 배열 요소의 값들을 모두 0으로 변경한다. 이 때, 자기 자신인 2는 변경하지 않는다.

3. 다음은 숫자 3부터 시작해서 차례대로 3의 배수에 해당하는 숫자를 인덱스로 가진 배열 요소의 값들을 모두 0으로 변경한다. 이번에도 역시 자기 자신인 3은 변경하지 않는다.

4. 숫자 4와 그 배수에 해당하는 숫자를 인덱스로 가진 요소들의 값은 모두 0이기 때문에, 다음 숫자인 5로 건너뛴다. 

5. 위의 과정을 판별할 숫자의 크기만큼 수행하면 결국엔 소수만 남아있게 된다.

 

 

 

에라토스테네스의 체를 코드로 구현하면 다음과 같다.

 

 

소수 판별하기 (Swift)

var number = 1000 // 판별할 숫자의 크기
var arr = Array(0...1000) // 판별할 숫자 크기만큼 배열 할당. 배열의 인덱스를 해당 배열의 요소 값으로 저장한다.

func solution() {
    arr[1] = 0 // 1은 소수가 아니기 때문에 0으로 바꿔주고, 아래 for 문을 2부터 시작한다.
    
    // 소수 판별 과정. 2부터 number까지 수행한다.
    for i in 2...number {
        if arr[i] == 0 { // 이미 배열 요소가 0이라면, 소수가 아니라고 판단한 것이므로 아래 코드 건너뛰기
            continue
        }
        
        var index = i * 2 // 다음 배수 확인하기
        while index <= number {
            arr[index] = 0 // 배수에 해당하는 인덱스는 배열 요소 값을 모두 0으로 변경
            index += i // 다음 배수 인덱스 구하기
        }
    }
    
    // 소수만 출력
    for number in arr {
        if number != 0 {
            print(number, terminator: " ")
        }
    }
}

solution()

 

 

위와 같이 구현하면 1000까지의 숫자 중 소수인 숫자만 출력할 수 있다.

 

 

 

또는 for-in stride 문을 사용하여 아래와 같이 구현할 수도 있다.

var number = 1000 // 판별할 숫자의 크기
var arr = Array(0...1000) // 판별할 숫자 크기만큼 배열 할당. 배열의 인덱스를 해당 배열의 요소 값으로 저장한다.

func solution() {
    arr[1] = 0 // 1은 소수가 아니기 때문에 0으로 바꿔주고, 아래 for 문을 2부터 시작한다.
    
    // 소수 판별 과정. 2부터 number까지 수행한다.
    for i in 2...number {
        if arr[i] == 0 { // 이미 배열 요소가 0이라면, 소수가 아니라고 판단한 것이므로 아래 코드 건너뛰기
            continue
        }
        
        for j in stride(from: i * 2, through: number, by: i) {
            arr[j] = 0 // 배수에 해당하는 인덱스는 배열 요소 값을 모두 0으로 변경
        }
    }
    
    // 소수만 출력
    for number in arr {
        if number != 0 {
            print(number, terminator: " ")
        }
    }
}

 

 

아래 코드는 이를 C++로 구현한 것이다.

 

소수 판별하기 (C++ 코드)

int number = 1000;
int a[1001];

void solution() {
	for (int i = 2; i <= number; i++) {
		a[i] = i;
	}
	for (int i = 2; i <= number; i++) {
		if (a[i] == 0) continue; // 이미 판별된 숫자는 건너뛰기
		for (int j = i * 2; j <= number; j += i) {
			// 특정 숫자의 배수부터 판별했다고 표시하기
			a[j] = 0;
		}
	}
	for (int i = 2; i <= number; i++) {
		if (a[i] != 0) cout << a[i] << "\n";
	}
}


solution()