[ 정수론 ] 소수 구하기 - 에라토스테네스의 체, 제곱근 기준 소수 판별, 구현까지

📝 에라토스테네스의 체

소수를 구하는 쉽고 빠른 방법

소수를 판별할 때, 아래와 같이 배수들을 지워나가면서 남은 수들을 소수로 판별하는 과정 !

 

이거 중딩? 때 다 해봤을거다ㅎㅎ

 

 

 

 

위의 그림에서 우린 1부터 50까지 소수를 판별하려고 한다. 

그래서 1부터 50까지 다 하나하나 배수를 지워야할 것 같지만, 실제로는 √50 이하의 수들만 확인하면 된다.

 

왜일까? 왜 하필 루트를 씌운 제곱근 값일까?

 

 

---

 

 

🔍 소수 판별 시에 제곱근 이하만 확인하면 되는 이유 🤔

 

1과 자기 자신이 아닌 약수가 하나라도 있다면, 그것은 소수가 아니다.

 

8

= 1 * 8

= 2 * 4

= 4 * 2

= 8 * 1

곱해서 8이 되는 조합들이다.

 

즉, 약수가 1,2,4,8이므로 소수가 아니다.

---

 

근데 여기서, 2가 나누어떨어지는 걸 봤는데, 굳이 4를 확인해야할까?

2 * 4든 4 * 2든 둘 중 하나만 나눠떨어지는 걸 봤다면, 이미 8은 소수 땡 탈락 ! 굳이 더 확인할 필요가 없다.

 

⭐ 즉, 곱해서 8이 되는 정수 조합 2개가 있을텐데, 그 중 하나라도 확인을 하면, 게임 끝이다.

나머지 하나는 고려할 필요가 없다 !

 

---

 

 

이러한 이유로  우리는 1~8까지의 소수를 판별할 때, 8까지 가지 않고도, 모든 소수를 판별해낼 수 있다.

 

50 이하의 소수를 알고싶다고, 50번 체로 걸러 소수 판별을 하는 수고를 안해도 된다는 것이다.

여기서 하필 딱 "제곱근"이 기준이 되는 이유는 무엇일까?

 

 

 

위의 진한 글씨를 다시 보자.

" 곱해서 8이 되는 두 수 " 

여기서 제곱근이 떠오른다. √8을 두 번 곱하면 8이 된다.

 

이 말의 의미는, 뭐든 곱해서 8이 되는 여러 정수 조합이 있을텐데,

그 조합의 두 수 중에 작은 놈은 항상 √8 보다는 작다는거다 !!

 

 

실제로 확인해보자. 곱해서 8이 되는 두 수의 조합들 중, 작은 놈들만 붉은색으로 표시했다.

8

= 1 * 8

= 2 * 4

= 4 * 2

= 8 * 1

 

1 < 2 < √8 < 4

 

 실제로 √8  이하만 조사를 한다고 해도, 2라는 약수가 이미 판별되었기 때문에

4를 추가로 판별하지 않아도 이미 소수가 아니란 걸 우린 안다.

 

이러한 이유로 n이하의 소수 판별은 2 ~ n 까지가 아닌, 2 ~ √ n까지만 조사한다.

 

 

---

 

[c++]  에라토스테네스의 체 구현

 

배수를 지우면서 소수를 판별하는 함수 구현 !

void isPrime(int n, vector<bool> &is_prime) {
    
    
    // 0과 1은 소수 아니므로 먼저 제거.
    is_prime[0] = is_prime[1] = false;
    
    
    // 루트 n까지만 소수 판별.
    for(int i=2; i<= sqrt(n); i++) {
        if(!is_prime[i]) { //소수 아닌걸로 이미 지워졌다면 건너뛰기 !
            continue;
        } 
        
        // i가 소수라면,
        for(int j=i*i; j<=n; j+=i) { // i의 "제곱"부터 다시 지워나가기
            is_prime[j]=false;
        }
    }
}

 

i의 제곱부터 지워나가는 이유

간단하다.

만약 5의 배수를 지워나갈 차례라고 치자.

 

5보다 작은 수와 5를 곱해서 만들어지는 수는 이미 지워졌다.

2*5 = 10 : 2 차례 때 지워짐

3*5 = 15 : 2 차례 때 지워짐

4*5 = 20 : 2 차례 때 지워짐

 

5보다 작은놈 * 5의 조합은 이미 지워졌기에,

따라서 5*5 부터 지워나가면 된다 !

 

---

에라토스테네스의 체 활용 예제 풀어보기 ! 

 

 

 

백준 1929번 소수 구하기

(실버 3)

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

(정답 코드)

#include <iostream>
#include <vector>

using namespace std;

// n 이하의 소수 모두 찾기
void findPrime(int n, vector<bool>& is_prime) {
    is_prime[0] = is_prime[1] = false;
    
    for(int i=2; i*i<=n; i++) { // = 빼먹지않게 주의
        
        if(is_prime[i]) {
            // 아직 안지워졌다면, 소수 ! 
            // 배수 지우기
            for(int j=i*i; j<=n; j+=i) {
                is_prime[j]=false;
            }       
        }
        
        else {
            // 이미 지워졌다면, 다음 !
            continue;
        }
        
    }
    
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n, m;
    
    // 입력
    cin >> m >> n;
    vector<bool> is_prime(n+1, true);  // 크기 n+1인 벡터 
    // !! 0번 인덱스는 사용하지 않으니 +1해주기 !! 아님 런타임 에러남

    
    
    // 연산
    findPrime(n, is_prime);
    
    
    
    
    // 출력
    for(int i=m; i<=n; i++) {
        if(is_prime[i]) {
            cout << i << '\n';
        }
    }
    
    return 0;
}

 

 

 

백준 6588번 골드바흐의 추측

(실버 1)

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

 

 

 

(정답 코드)

#include <iostream>
#include <vector>

using namespace std;

//소수들을 남기고, 나머지는 지워나가는 벡터
    vector<bool> is_prime(1000001, true); 
    
// 에라토스테네스의 체로 범위 내의 소수들 판별.
int findPrime() {
    
    is_prime[0]=0;
    is_prime[1]=0;
    
    for(int i=2; i*i<=1000001; i++) {
        if(!is_prime[i]) { //이미 false이면 검토 X
            continue; //아래 무시하고 바로 다음 반복
        } 
        
        for(int j=i*i; j<=1000001; j+=i) {
            if(!is_prime[i]) { //이미 false이면 검토 X
                continue;
            }
            
            is_prime[j]=false;
        }
    }
    
    return 0;
}


int main()
{
    //시간초과 해결
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
   
   //소수 판별 (아리스토테네스의 체)
    findPrime();


    int n;
    cin >> n;

    
    while(n!=0) {
        
        int flag=0;
        
        int a=0;
        int b=0;
        
        
        //n 미만의 소수 b, 그리고 a=n-b. a가 소수면 그대로 a,b 확정 및 출력

        for(int i=n-1; i>2; i-=2) { // 홀수 소수만 체크하면 되니까 i-=2
            flag=0;
            
            if(is_prime[i]) { //소수면 true
                b=i;
                a=n-b;
                if(is_prime[a]) {
                    flag=1;
                }
            }
            
            if(flag==1) {
                cout << n << " = " << a << " + "<< b << '\n';
                break;
            }
        }
        
        if(flag==0) {
            cout << "Goldbach's conjecture is wrong." << "\n";
        }
        
        //다시 또 입력받고 반복
        cin >> n;

    }

    return 0;
}

 

---

 

 

사담...

 

알튜비튜 수업을 들었는데, 왜 루트 n까지인지 잘 이해가 되지 않았다..

노트에 끄적이며 고민하는데 갑자기 해답을 찾아섷ㅎ 

 

루트 n을 두 번 곱하면 n이 되니까..! 약수 중 절반은 다 루트 n보다 작구나..! 하는 깨달음이 생겼다..ㅎ

사실 쉽고 사소한 것이지만, 이렇게 원리적으로 접근해서 완전히 이해가 되어야 기억에도 더 오래가는 법이다 ㅎㅎ..

나같은 사람에게 해답을 나누고자 쉽게 예시도 들며 정리를 해봤다. 이해가 되시나요 ...!! (그리고아무도없었다)

 

이미 글을 잘 써두신 분들은 사실 많다 ㅎㅎ 그냥 나는 진짜 내 정리용..으로만 쓰는거지

그치만 봐쥬세요 기술블로그란 공간이 마치 하나의 강의실처럼.... 제자를 가르치는 심정으로 세세하고 쉽게 쓰고있다.

이런 나를 보면, 나중에 유튜브 강의나 올려야 할듯 ㅎㅅㅎ

 

내가 머찐 선생님들의 글을 보고 이해를 하듯, 어느 누군가는 내 티스토리를 보고 해답을 얻는 순간이 있길 :)