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

에라토스테네스의 체 란

배수들을 미리 찾아서 지운 후 소수를 찾는 알고리즘이다.

 

과정

1. 2부터 원하는 수 까지 배열에 0이 아닌 그 값을 집어 넣는다.

2. 2부터 차례대로 원하는 수까지 반복문을 돌며 그 숫자의 배수들을 0으로 만들어 배열에 집어 넣는다.

3. 반복문을 전부 돌면 0이 아니면 값을 하나씩 출력한다.

 

코드

number = 100000
int array[number];

for(int i=2; i<number.size(); i++){
	array[i] = i;
}

for(int i=2; i<number; i++){
	for(int j=i*2; i<number; j+=i){
    	if(array[j]==0) continue;
		array[j]=0;
}
}

for(int i=2; i<number; i++){
	if(array[i]!=0) cout << i << ", ";
}