[백준 1929] 소수 구하기 (에라토스테네스의 체)

• 안녕하세요. BlockDMask 입니다.

• 오늘의 문제를 포스팅 해보겠습니다.
  클라이밍 하고와서 손이 부들부들 떨리는데;;
  24시가 되기전에 올려야하니, 샤워도 안하고 폭풍 포스팅을 해보겠습니다.

• 소수를 구하는 문제인데;;
  에라토스테네스의 체 (소수 구하는 방법) 방법을 이용하여 풀어야하는 문제입니다.

0. 제목

• 백준 1929 소수 구하기

• BOJ 1929 소수 구하기

1. 문제설명

1 <= a <= b <= 1,000,000

a~b 까지 숫자의 범위를 집어 넣으면

그 숫자 사이에 있는 소수(prime number)들을 출력하는 문제입니다.

2. 풀이과정

일반적인 방법으로 소수를 구하면 "시간초과"가 나옵니다.

(자신보다 작은수로 % 했을때 나머지가 0인지)

에라토스테네스의 방법으로 풀어야 "맞았습니다" 가 나옵니다.

에라토스테네스의 방법을 간단히 과정을 보이겠습니다.

자세한 이론은 맨 밑에 URL 넣어두겠습니다.

1~20까지의 소수를 구한다고 했을때.

[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20]

1) 1은 소수가 아니니 버린다.

[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20]

2) [2]는 소수이다. -> 그러면 2의 배수는 소수가 아니다. -> 지운다.

[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20]

3) [3]는 소수이다. -> 그러면 3의 배수는 소수가 아니다. -> 지운다.

[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20]

3) [4]는 건너뛰고-> [5]소수이다. -> 그러면 5의 배수는 소수가 아니다. -> 지운다.(지워져있다.)

[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20]

3) [6]는 건너뛰고-> [7]소수이다. -> 그러면 7의 배수는 소수가 아니다. -> 지운다.(지워져있다.)

[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20]

4) [8, 9, 10]는 건너뛰고-> [11]소수이다. -> 그러면 11의 배수는 소수가 아니다. -> 지운다.(범위를 넘는다)

.

.

.

[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20]

이런식으로 쭉쭉쭉 가면서 이미 정해진 소수의 배수인 것들을 지워서 소수를 구하는 방법이

 "에라토스테네스의 체" 입니다.

근데 가만히 보면.

2의 배수를 지우고 3의 배수를 지우고 하면.

5의 배수를 지울때 2, 3의 배수들이 이미 한번 지운게 겹칩니다.

왜냐면 5x2 랑 5x3이니까요!

이런 중복이 없을때 부터 배수를 지우려면

제곱한 수 부터 배수를 지우면 됩니다.

5의 배수를 지운다면, 5의 제곱인 25부터 25+ 5,  25+ 2*5,  25+ 3*5  . . . . . 이런식의 배수를 지웁니다.

그러면 그전에 이미 지워져있는 배수들을 건너 뛰게 됩니다.

i 는 0 부터 증가.

이런방식으로 지우면 됩니다.

이번 문제에서는 숫자의 범위가 1,000,000 이므로

제곱을 했을때 1,000,000을 넘으면 break를 걸었습니다.

코드로 표현해보겠습니다.

3. 코드

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
 
// 1<= a <= b <= 1,000,000
int main(void){
    int a,b;
 
    scanf("%d %d", &a, &b);
 
    //최대치 크기만큼 동적할당을 합니다
    bool * arr = new bool[b+1];
 
 
    //배열을 true로 초기화합니다
    for(int i=0; i<b+1; i++){
        arr[i] = true;
    }
 
 
    int j;  //제곱의 수를 받을 변수
 
    for(int i=2; i<b+1; i++){
 
        if(arr[i]){ //true이면
 
            if((unsigned int)pow(i, 2) > 1000001){
                //제곱이 범위를 넘으면 for 문을 나옵니다
                break;
            }else{
                //이미 있는 소수들의 배수들을 지워줍니다.
                for( j = (int)pow(i, 2) ; j < b+1 ;){
                    arr[j] = false; //소수가 아닌 수들을 false로 바꿔줌
                    j = j+i;
                }
            }
 
        }
    }
 
    //1인경우를 제외해야하므로 a가 1이 들어왔을때, 2로 만들어줍니다
    if(a == 1) a++;
 
 
    //true이면서, a보다 큰 값들을 출력!
    for(int i=a; i<b+1; i++){
        if(arr[i] && i>= a)    printf("%d\n", i);
    }
 
    delete []arr; // 동적할당 해제
    return 0;
}

4. 인증

문제 출처 : https://www.acmicpc.net/problem/1929

원리 출처 : http://terms.naver.com/entry.nhn?docId=1179083&cid=40942&categoryId=32204

감사합니다. 이번문제에서는 배운게 많습니다.

이렇게 소수를 구하는 방법이 있었다니 한 분야의 전문가들은 클라스가 다름을 느꼈습니다.