[Prime] 에라토스 테네스의 체 | C++ / Cpp

이전 포스팅 https://dusty-wznt.tistory.com/85

에서 Prime에 대해 다뤘고 그와 동시에 에라토스 테네스의 채의 원리를 

너무나도 완 벽 하 게

이해를 해버렸.땨.

 

# 에라토스 테네스의 체

• 주어진 integer x가 prime인지에 대한 여부를 쉽게 판별할 수 있도록 processing 해주는 알고리즘.
• prime 여부는 크기가 n인 array에 저장되며
  • (이해를 돕기 위해 sieve라고 하겠다. sieve == 체)
• i>2에 대하여 sieve[i] ==0이면 i는 prime이고 sieve[i]==1이면 i는 !prime이다.
• 이처럼 배열은 해당 index가 prime인지에 대한 여부를 저장한다.

이렇게 말이다.

 

여기서 에라토스 테네스의 채를 구현할 때 key idea가 될 조건은

앞서 포스팅 했던 n =ab(1<a,b<n)이다.

1. sieve의 값을 모두 0으로 초기화 하고
2. i=2 부터 processing을 진행하며 배열의 값을 변경하여준다.
3. sieve[i]의 값이 0으로 확정인 경우 (== prime) 2i보다 크거나 같은 i의 모든 수 j에 대하여 sieve[j]=1로 변경하여 !prime을 저장한다.

 

코드를 보며 추가적인 설명을 진행하겠다.

 

 

# 에라토스테네스의 체 | Cpp

for(int x=2;x<=n;x++){
	if(int(sieve[x]) continue; 
    for(int u=2*x; u<=n; u+=x){
    	sieve[u]=1;
    }
}

 

• x가 !prime일 경우 배열이 저장하고있는 값은 1이므로 더 변경하지 않고 continue.
• x가 prime일 경우 x를 제외한 n보다 작은 x의 배수들을 모두 탐색하여 값을 1로 변경한다.

 

각i에 대하여 최대 n/i개의 sieve array 값을 바꾸무로

에라토스테네스의 체의 시간 복잡도는 O(nlogn)이다.

 

아아아아ㅏㅇ주.

후련하군. ><