[알고리즘] 에라토스테네스의 체

활용

소수를 찾을 때 활용

Think

2부터 시작한 수의 배수를 자기자신을 제외하고 배열의 수를 0으로 넣어준다
=> 0이 아닌 수가 소수!

방법 1

• 배열을 int형으로 제작하는 경우

1. 소수를 구하고 싶은 수까지 배열에 index를 넣어준다

for(int i = 2; i < N; i++){
	arr[i] = i;
}

2. 2부터 시작한 수의 배수를 자기자신을 제외하고 0을 입력

for(int i = 2; i < N; i++){
	if(!arr[i]) continue; // 0이면 넘어가기
    for(int j = i + i; i < N; i++){
    	a[j] = 0;
    }
}

3. N까지의 소수 출력

for(int i = 0; i < N; i++){
	if(!arr[i]) cout << arr[i] << "\n";
}

방법 2

• 배열을 bool형으로 제작하는 경우

1. 2부터 소수를 구하고 싶은 수까지 배열에 1(true) 입력

#include <algorithm>

fill(arr + 2, arr + N, 1);

2. 2부터 시작한 수의 배수를 자기자신을 제외하고 0(false)을 입력

for(int i = 2; i < N; i++){
	if(!arr[i]) continue; // 0이면 넘어가기
    for(int j = i + i; i < N; i++){
    	a[j] = 0; // false
    }
}

3. N까지의 소수 출력

for(int i = 0; i < N; i++){
	if(!arr[i]) cout << i << "\n";
}