[알고리즘]JAVA- 에라토스테네스 체

에라토스테네스의 체 란?

소수를 판별하는 알고리즘이다.

소수들을 대량으로 빠르고 정확하게 구하는 방법이다.

 

에라토스테네스의 체 원리

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

 

n*2 는 앞선 2의 배수를 제거하는 과정에서 이미 지워졌다. (n*2는 n의 배수이지만, 2의 배수이기도 하니까)

n*3 은 앞선 3의 배수를 제거하는 과정에서 이미 지워졌다. (n*3은 n의 배수이지만, 3의 배수이기도 하니까)

n*5 는 앞선 5의 배수를 제거하는 과정에서 이미 지워졌다. (n*5는 n의 배수이지만, 5의 배수이기도 하니까)

...

이처럼 n과 곱해지는 값이 n 이전의 수일때는, 이전 과정에서 이미 지워졌을 것이다.

 

그렇다면 남은 것은 n*n이다. 

n*n은 n의 배수를 제거하는 과정을 거치지 않았지만

n*n가 N(주어진 자연수)보다 크다면, 범위를 벗어났으므로 굳이 소수인지 아닌지 고려할 필요가 없다. 

 

그래서 n*n<=N 이면 반복문을 돌아서 n*n가 소수인지 아닌지 판정하고,

          n*n>N 이면 굳이 반복문을 돌지 않고 종료한다.

 

1. 배열을 생성하여 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

 

구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(solution(N));
    }

    public static int solution(int N) {
        int answer = 0;
        int[] arr = new int[N + 1]; // N 또한 배열에 포함해야한다.

		//루프를 돌면서 배열에 숫자등록 
        for (int i = 2; i <= N; i++) {
            arr[i] = i;
        }

		//하나씩 지워주자.
        for (int i = 2; i * i <= N; i++) {
            for (int j = i * i; j <= N; j += i) { //i의 배수 증가
                arr[j] = 0;
            }
        }
        for (int i = 2; i <= N; i++) {
            if (arr[i] != 0) {
                answer++;
            }
        }

        return answer;
    }
}

 

---

 

소수구할 때는 에라토스테네스 체 방식을 쓰면 빠르게 구할 수 있다.

 

한번 쭉 배열에 담고 N의 제곱근 보다 작은 소수들의 배수를 지워나간 뒤

배열의 값이 0 이 아닌것만 출력하는 기법!