[알고리즘] 소수(에라토스테네스 체)

이름부터 생소했다,, '에라토스테네스 체'

설명

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

입력
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

출력
첫 줄에 소수의 개수를 출력합니다.

예시 입력1: 20

예시 출력1: 8

---

기존 풀이코드

import java.util.Scanner;

public class Main {
    public int solution(int n){
        int answer=0;
        boolean isPrime=true;
        for(int i=2; i<=n; i++){
            for(int j=2; j<=Math.sqrt(i); j++){
                if(i%j==0)  isPrime=false;
            }
            if(isPrime) answer++;

            isPrime=true;
        }



        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(T.solution(n));
    }
}

"n까지의 수에서 본인의 제곱근이하의 수로 나누어진다면 소수가 아니다" 를 활용해서 풀었지만, 이거보다 더 빠르게 구하는 방식이 "에라토스테네스 체"이다.

쉽게 설명하면 for(int i=2; i<=n; i++)를 통해
i로 나누어지는 수를 반복문을 통해 "1" or "true"로 체킹하여 소수가 아닌 것을 걸러내면 된다.

ex)
2로 나누어지는 수 들은 전부 1로 표시
3으로 나누어지는 수 들은 전부 1로 표시
.......
i로 나누어지는 수 들은 전부 1로 표시해서 n까지 가는 것이다.

---

에라토스테네스체를 반영한 코드

import java.util.Scanner;

public class Main {
    public int solution(int n){
        int answer=0;
        int[] arr = new int[n+1];
        for(int i=2; i<=n; i++){
            if(arr[i]==0){
                answer++;
                for(int j=i; j<=n; j=j+i)   arr[j]=1;
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(T.solution(n));
    }
}

• 인덱스는 0부터 채워지므로 객체를 n+1만큼 만들어준다.
• 배열 생성할 때 초기에 '0'으로 초기화 되서 채워지므로 소수 2는 카운팅이 된다.

자세한 원리가 궁금하다면?

위키백과-에라토스테네스 체

https://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