[알고리즘] 2-5 소수, 에레토스테네스 체(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 간략한 문제 설명, 예습 풀이 코드, 강의에서 설명하는 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/02-05
• 문제 설명 : 1~n까지의 소수 개수를 출력

에라토스테네스 체

고대 그리스 수학자 에라토스테네스가 만들어낸 간단하고 빠르게 소수를 찾는 방법이다. 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스 체'라고 부른다.

계산 방법

n이하의 수들 중에 소수를 찾는다고 가정하고, 1~n까지 숫자를 차례대로 쭉 적는다.

1. 자연수 1을 제거한다.
2. 2를 제외한 2의 배수를 제거한다.
3. 3을 제외한 3의 배수를 제거한다.
4. 다음은 4의 배수를 지워야하지만, 2의 배수에서 이미 지웠기 때문에 생략
   ...

위와 같이 순차적으로 2,3,5, ... n까지 제거되지 않고 남아있는 수들의 배수를 지우다 보면 지워지지 않고 남게 되는 수들이 있는데 그것들이 소수이다.

풀이

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

public class Main2_5 {

    public static int solution(int n) {
        int[] arr = new int[n+1];//숫자와 배열 인덱스를 맞추기위해 +1
        int count = 0;

        for (int i = 2; i <= n; i++) {
            if (arr[i] == 0) {
                count++;
                for (int j = i*2; j <= n; j+=i) { //i의 배수를 제거하는 과정
                    arr[j] = 1;
                }
            }
        }

        return count;
    }

    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));
    }
}