[인프런 알고리즘] Chapter 2, 5번 문제(소수(에라토스테네스의 체))

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

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

public class sec02_05 {
    public static int solution(int N) {
        boolean[] arr = new boolean[N + 1];
        Arrays.fill(arr, true);

        int count = 0;
        for(int i = 2; i <= Math.sqrt(N); ++i){
            if(arr[i]){
               for(int j = i * i; j <= N; j += i) arr[j] = false;
            }
        }

        for(int i = 2; i <= N; ++i) if(arr[i]) ++count;
        return count;
    }

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

 

설명

for(int i = 2; i <= Math.sqrt(N); ++i){
    if(arr[i]){
        for(int j = i * i; j <= N; j += i) arr[j] = false;
    }
}

• 2부터 N의 제곱근까지 반복문을 실행한다. 이 범위 내의 숫자들로 모든 배수를 체크하면 충분하기 때문이다.
• i가 소수(arr[i]가 true)인 경우, i의 배수들을 모두 소수가 아니라고 표시한다(false로 설정).
• i * i부터 N까지 i의 배수들을 false로 설정한다. i 이전의 배수들은 이미 처리되었기 때문이다.

 

https://www.youtube.com/watch?v=9rLFFKmKzno&ab_channel=%ED%95%9C%EB%B9%9B%EB%AF%B8%EB%94%94%EC%96%B4