소수 찾는 알고리즘, 에라토스테네스의 체

어떤수 N의 약수를 찾기 위해선 sqrt(N)까지의 수를 나누어보며 조사하는것이 가장 빠른 약수파악 알고리즘이다.

 

따라서 N이 소수(Prime)인지 판별하기 위해서는 N의 제곱근까지의 수 만큼 반복문으로 나누어 주면 된다.

 

다음은 N 개의 수를 입력받고 그 중에 소수가 몇개인지 찾는 BOJ 1978번 문제이다.

#include <iostream>
int main(){
    //모 임망

    int N=0;
    std::cin>>N;
    int sosu[N];
    int cnt = N;
    
    for(int i=0;i<N;i++){
        std::cin>>sosu[i];
        if(sosu[i] == 1)
            cnt--;
    }

    for(int i=0;i<N;i++){
        for(int j=2;j*j<=sosu[i];j++){;
            if(sosu[i]%j==0){
                cnt--;
                break;
            }
            else
                continue;
        }
    }

    std::cout<<cnt;
}

1. N과 N개의 소수를 배열로 먼저 입력받는다.

2. 각 수에 대해 그 수의 제곱근 까지 for문안에서 나누어 본다.

3. 1~제곱근 내 범위에서 나뉘어 지는 수가 있을경우 그 수는 소수가 아니므로 cnt-- 해주고 반복문을 탈출한다.

4. 반복문을 통과하면 그 수는 소수이다.

5. cnt를 출력한다.

 

이런식의 알고리즘이다.

 

이렇게 특정수를 제시하고 소수 인지 아닌지를 판별해 보았다. 

해당 개념을 확장해 1~N 까지의 소수의 개수를 세는 가장 적합한 알고리즘이 에라토스테네스의 체 이다.

 

 

에라토스테네스의 체

 

https://commons.wikimedia.org/wiki/File:Sieve_of_Eratosthenes_animation.gif

File:Sieve of Eratosthenes animation.gif - Wikimedia Commons

 

에라토스테네스의 체 개념을 가장 이해하기 쉽게 표현한 그림이다.

1. 먼저 이 개념을 이해하기 전에 모든 수는 소수들의 곱으로 표현된다는 사실을 알 필요가 있다.

(예를들어 34의 경우 2x17 이다, 2는 소수이고 17도 소수이다.)

2. 그래서 에라토스테네스의 체 개념은 1~N 까지 수를 증가시키다가, 소수를 찾고 소수를 찾은 즉시 그 소수들의 배수를 제외시킨다. 그러면  남는수는 결국 소수일 것이다. 라는 개념이다.

3. 증가의 범위 역시 sqrt(N) 까지 인데, sqrt(N) ~ N 까지 수 중 소수가 아닌 수는 존재할 수 없다.

sqrt(N) ~ N 까지의 수는 sqrt(N)를 포함한 이전의 수의 배수이다. 위에서 풀었던 소수판별 개념과 동일하다. 

대수적으로 설명하면 어떤수 K의 경우

 

K1 = (소수) x (임의의 수K2) 로 표현된다.

임의의수 K2가 소수가 아니라면,

K2 = (소수) x (임의의 수K3) 로 표현된다.

... 과정을 거치고 나면 

K1 = (소수1) x (소수2) x ... x (소수n) 이다.

 

코드로 풀어보자, 아래는 M ~ N 까지의 수 중 소수를 출력하는 Java 코드이다 (BOJ 1929)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static boolean[] TF;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
        StringTokenizer st = new StringTokenizer(br.readLine());


        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();

        TF = new boolean[N+1];
        prime();

        for(int k=M;k<=N;k++){
            if(!TF[k])
                sb.append(k).append('\n');
        }

        System.out.println(sb);

    }

    public static void prime(){

        TF[0] = true;
        TF[1] = true;


        for(int i=0;i*i<=TF.length;i++){
            if(TF[i])
                continue;
            for(int j=i*i;j< TF.length;j+=i)
                TF[j]=true;
        }

    }

}

 

 

소수 찾는 Prime 함수

1. M~N 까지의 수 중 에라토스테네스의 체 를 구현하기 위해 크기가 N+1인 배열을 선언한다. TF[N+1]

2. 이후 0과 1 은 소수가 아니기에 true로 정의한다.

3. N의 제곱근 까지 조사한다.  이때 TF[i] 가 소수가 아니라고 이미 판단된 수 일경우, 넘어간다

4. TF[i] 가 소수(false) 로 추정되는 경우, 이 수의 배수들을 for문으로 정의시켜 준다. (이때 i 는 소수이므로, i+i 부터 시작한다.)

5. 그리고 배수인 수들의 bool형 배열을 true로 선언해준다.

public static void prime(){
       
        TF[0] = true;
        TF[1] = true;
        
        for(int i=0;i*i<=TF.length;i++){
        
            if(TF[i])
                continue;
                
            for(int j=i+i;j< TF.length;j+=i)
                TF[j]=true;
        }

    }
}

6. 이후 false 인 배열의 수를 세면, 소수의 개수가 나오고 false인 배열의 번호를 출력하면 소수가 출력된다. 

 

 

Main 함수

 public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());


        StringBuilder sb = new StringBuilder();

        TF = new boolean[N+1];
        prime();

        for(int k=M;k<=N;k++){
            if(!TF[k])
                sb.append(k).append('\n');
        }

        System.out.println(sb);

    }

- StringBuilder 를 사용해 소수를 출력 해 주었다.