2-5 소수 구하기 (에라토스테네스 체) (Java)

✏️ 문제

---

설명

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

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

입력

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

출력

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

예제입력 20
예제출력 8

---

✏️ 코드

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(solution(n));
    }
    
    public static 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;
    }
}

소수를 구하기 위해서 배열에 담긴 숫자 모두 하나씩 반복문을 통해서 구할 수 있지만 숫자의 양이 많아진다면 실행시간이 엄청 길어질 것이다.

그래서 소수를 구하는 효율적인 알고리즘인 에라토스테네스의 체가 있다.

배열을 모두 0으로 초기화 시키고 해당 인덱스가 0이면 소수, 1이면 소수가 아닌 것으로 계속 걸러내면 된다.

우선 소수는 1과 자기 자신만을 약수로 갖고 있다.

2부터 시작하여 소수이면 answer++를 통해 소수의 개수를 누적시킨다.

그리고 2의 배수들은 소수가 아니기 때문에 모두 1로 바꿔준다. 바로 j=j+i를 통해서 해당 숫자의 배수에 모두 표시한다.

다음 3으로 넘어가면 3번 인덱스는 0이기 때문에 answer++를 하고 다음 for문에서 3의 배수들은 모두 1로 바꿔주며 반복하는 방식이다.

---

정리