백준 C++ 1978번 소수 찾기 ( 에라토스테네스의 체 )

---

 

사실 소수 찾는 거 무슨 이름이 있었는데..

막 뭔 체였는데..

2로 나누고.. 뭐 하고..?? 막 그랬는데..

 

1도 필요없고 2는 안되고 3부터 되는데

..

소수란 1보다 크면서, 1과 자기 자신만으로 나누어 떨어지는 수

 

제씨에게 해답을 요청했다.

 

1000개까지가 최대기 때문에

이중포문으로 푸는 게 가능했다.

 

bool값으로 소수인지 아닌지 판별하고

소수 = prime

a < 2면 일단 넘긴다.

왜냐하면 1,2 둘다 소수가 아니기 때문!

그래서 2부터 j*j <= a까지

이렇게 제곱을 사용하는 이유는

보통 숫자의 경우 a*b로 이루어져 있는데

같은 숫자를 기점으로

b*a가 되게 된다.

36의 경우

4 9 / 6 / 9 4 

이렇듯 말이다!

 

그래서 j*j <=a까지 해주면서

+ 배수가 있다면 false 해주기

 

그리고 마지막에 prime가 true 면 cnt++ 해주기

 

 

그리고 대망의

 

에라토스테네스의 체

소수를 찾는 가장 빠른 방법

소수의 배수를 모두 지우면 남는 건 소수뿐

 

이 알고리즘은

 

1. 배열 필요

범위만큼의 배열을 만들고 모두 소수(true)로 채운다.

0과 1 제외

 

2. 배수 지우기

2부터 시작해서 숫자를 하나씩 확인한다.

 

3. 체 거르기

지워지지 않은 ( 소수인 친구들 )

그 소수의 배수를 찾아서 false 해준다.

 

4. 반복

이 과정을 sqrt(N)만큼 반복한다.

숫자가 작을 땐 j*j 같은 걸로도 해도 된다.

 

식을 해보면!

 

vector <bool> v(n+1, true);

불값 벡터를 만들고 크기는 범위 +1까지 true로 초기화!

 

v [0] = v [1] = false;

0과 1은 제외

 

for (int i = 2; i * i <= n; i++)

2부터 제곱근 n까지 

 

if(v [i])

만약에 v [i]가 소수면!

 

for (int j = i * i; j <= n; j += i) 

v = false;

소수의 배수 모두 제거

// 1. n까지의 소수 판별 배열 준비
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;

// 2. 에라토스테네스의 체 공식
for (int i = 2; i * i <= n; i++) { // 루트 n까지만 확인
    if (is_prime[i]) { // i가 소수라면
        for (int j = i * i; j <= n; j += i) { // i의 배수들을 모두 제거
            is_prime[j] = false;
        }
    }
}

 

이 에라토스테네스 체를 이 문제에 적용하면

 

이 문제에서는 

숫자의 범위가 1부터 1000까지 기 때문에

bool값으로 미리 1부터 1000까지 소수만 따로 빼 주고

cnt 해주면 된다.

 

---

 

에라토스 어쩌고 체

생각보다 어지러운걸? 자주자주 머릿속에 적어두어야겠다.

 

만나기 싫은 문제긴 하다.

그래도 알아야 할 것.

소수 구할 때 i*i 해줘서 범위 줄이는 것!

배수도 지워줘야 해서 j = i*i ; j+= i 해주는 것!

 

내가 내일 기억할 수 있을까?...