에라토스테네스(Eratosthenes)의 체

소수란?

소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. 이와 같은 의미로 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다. 

 

소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체가 있다. 에라토스테네스의 체 원리를 살펴보자.

 

에라토스테네스의 체

원리

1) 구하고자 하는 소수의 범위만큼 1차원 배열을 생성2) 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.3) 배열의 끝까지 (2)를 반복한 후 배열에 남아 있는 모든 수를 출력한다.

1부터 30까지의 수 중 소수를 구하는 예시를 보면서 원리를 이해해보자. 

1) 먼저 주어진 범위까지 배열을 생성한다. 이때 1은 소수가 아니므로 삭제하고 배열은 2부터 시작한다.

 

2) 선택한 수의 배수를 모두 삭제한다. 현재는 2의 배수를 전부 삭제했다. 

 

3) 다음 지워지지 않은 수를 선택하낟. 즉 3을 선택하고 선택한 수의 모든 배수를 삭제한다. 

 

4) 앞의 과정을 배열의 끝까지 반복

 

5) 삭제되지 않은 수를 모두 출력

 

코드로 구현하기

에라토스테네스의 체를 이용하여 num까지의 소수를 구하는 코드

1)num 값을 받고 num+1 크기의 배열 생성하고 num까지 값 넣기

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int num = Integer.parseInt(st.nextToken());
        int [] list = new int[num+1];

        for(int i=1; i<=num;i++){
            list[i]=i;
        }

 

2) 소수임을 확인하고 소수의 배수를 0으로 치환

for(int i=0; i<list.length; i++) {
    int number=list[i];
    int check = 0;
    for (int j = 1; j <=Math.sqrt(num); j++) {
        if (number % j == 0) check++;
    }
    if (check == 2) {
        //소수일 때 작동
        //num까지 배수의 index값을 0으로 만들기
        for(int k=2; k<=num/number; k++){
            int drainage = number*k;
            list[drainage]=0;
        }

    }
}

3) 0인 값을 제외하고 출력

for (int i : list) {
    if(i==0)continue;
    System.out.println(i);

}

전체코드

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

public class 에라토스테네스 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int num = Integer.parseInt(st.nextToken());
        int [] list = new int[num+1];

        for(int i=1; i<=num;i++){
            list[i]=i;
        }
        list[1]=0;
        //소수임을 확인하는 로직
        for(int i=0; i<list.length; i++) {
            int number=list[i];
            int check = 0;
            for (int j = 1; j <=Math.sqrt(num); j++) {
                if (number % j == 0) check++;
            }
            if (check == 2) {
                //소수일 때 작동
                //num까지 배수의 index값을 0으로 만들기
                for(int k=2; k<=num/number; k++){
                    int drainage = number*k;
                    list[drainage]=0;
                }

            }
        }

        for (int i : list) {
            if(i==0)continue;
            System.out.println(i);

        }

        System.out.println("end");
    }

}