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

문제링크 : www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

 

 

 

접근 방식 1 

 

페르마의 정리 이용ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95#%ED%8E%98%EB%A5%B4%EB%A7%88_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

소수판별법 - 위키백과, 우리 모두의 백과사전

gcd(a,p)  = 1 , a<p and p가 소수이면 a^p-1 (mod p) 는 1과 합동이다.

 

그러나 a = 8, p = 9일때, 8^8 = 16777216이어서 이를 9로 나눈 나머지는 1인데, 9는 소수가 아니므로 예외가 발생한다.

 

#include <iostream>
#include <cmath>

using namespace std;

int gcd(int p, int a){
    
    int c;
    while(a!=0){
        c = p%a;
        p = a;
        a = c;
    }
    return p;
}

int main(){
    
    int M, N;
    cin >> M >> N;

    for(int p = M; p<=N; p++){

        for(int a = 2; a<p; a++){

            if(gcd(p,a) == 1){

                int chk =((int)pow(a,p-1)) % p;
                if(chk == 1){
                    cout << "a: " << a << " /p: " << p << endl;
                    break;
                }
            }
        }
    }

    return 0;
}

 

 

 

접근 방법 2

Miller-Rabin Primality Test 를 이용해보자. 

#include <iostream>
#include<cstdlib>
#include<ctime>
#include<cmath>


using namespace std;


bool Test(int a, int n){
    
    
    int u=0, t=0;
    int k = n-1;
    int tmp = k;
    if(k%2 != 0){   //k홀수 즉 n짝수(합성수 이므로 true return)
        return true;
    }
    
    while(k>=2){
        if(k%2 == 0) {
            t++;
            k /= 2;
        }
    }
    
    u = tmp / pow(2,t);
    
    int x0 = (int)pow(a,u) % n;
    int x=0;
    for(int i = 1; i<=t; i++){
        
        x = (x0*x0) % n;
        
        if(x==1 && x0 !=1 && x0!=n-1){
            return true;
        }
        
        x0 = x;
    }
    if(x!=1) return true;
    
    return false;

}


int main(){
    
    int M, N;
    cin >> M >> N;

   srand((unsigned int)time(NULL));

    for(int n = M; n<=N; n++){
        
        bool chk = true;
        for(int s = 0; s<10; s++){
            
            int a = rand();
            while(a>=n){a = rand();}
            
            if(Test(a,n) == true){
                //합성수
                chk = false;
                break;
            }
            
        }
        
        
        if(chk){ //s번 다 도는 동안 Test()가 모두 false 이면
            //n은 소수
            cout << n << endl;
        }
        
        
        
        
    }
    
    
    
    return 0;
}

시간 초과가 떴다.

 

 

 

 

 

 

 

 

접근 방법 3

 

많은 사람들이 선택한 '에라토스테네스의 체' 방법을 이용했다. 

참고 : ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

 

2가 소수니까 2의 배수는 소수가 아니다. 그러므로 2의 배수를 쭉 지운다.

3도 소수니까 3의배수는 소수가 아니다. 그러므로 3의 배수를 쭉 지운다.

 

이때 주의할 점은 j의 시작값이다. i*j(j<i)까지는 이미 검사했으므로 j 시작값을 i*2 에서 i*i로 개선할 수 있다.

i=5, j=3일때를 예로 들어보자.

5*3 = 15까지는 이미 i=3일때 검사가 됐다. 그러므로 j시작 값을 10(소수 5의 첫번째 배수)이 아닌 25부터 할 수 있는 것이다. 

더 자세히 따져보기 위해 실제로 2~24의 수 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24  을 봐보자.

 

(i = 2) 2의 배수 4,6,8,10,12,14,16,18,20,22,24 를 checked 한다

(i = 3) 3의 배수 6,9,12,15,18,21,24 를 checked 하는데 사실 이 중 2의 배수들은 i=2일때 이미 checked된 상태이다.

(i = 4) 4의 배수 -> arr[4] = 1이므로 볼 필요도 없이 Pass

(i = 5) 5의 배수 10,15,20 -> 이미 checked된 상태이다.

 

그러므로 j시작값을 i*i 부터 할 수 있는 것이다. 그러면 중복을 제거할 수 있다.

 

#include <iostream>
#include<cstdlib>
#include<ctime>
#include<cmath>


using namespace std;

int arr[1000001] = {0};
int main(){
    
    
    int M, N;
    cin >> M >> N;

   
    arr[1] = 1; //1은 소수 아님
    
    
    
    for(int i = 2; i*i <= N; i++){
        
        if(arr[i]==0){
            for(int j = i*i; j<=N; j+=i){
                arr[j] = 1;
            }
        }
    }
    
    
    
    for(int i = M; i<=N; i++){
        if(arr[i] == 0 ) cout << i << "\n";
    }
        
    return 0;
}