<2.5> 소수 (에라토스테네스 체)

문제
: 자연수 N이 입력되면, 1부터 N까지의 자연수 중 소수의 개수를 출력하시오
( 2 <= N <= 200,000)
Ex) 20이 입력되면 -> 1부터 20 사이의 자연수 중 소수는 2,3,5,7,11,13,17,19 총 8개이므로 -> 8이 출력되어야 함

이 문제의 요구사항은 문제에서 주어진대로 1부터 입력한 자연수 까지의 소수의 개수를 count하는 것이다.

나는 시행착오를 겪어 아래와 같은 2가지 해결책을 사용하였다.

[해결책]
1. 첫 번째 로직

• 단순히 2부터 입력한 수 N까지의 모든 자연수에 대해서 loop을 돌면서
• 각 자연수 별로 소수 판정을 하여 - 소수인것만 count
• 이때 소수판정은 다음의 로직
  • 소수의 정의가 1과 자기 자신만으로 나누어 떨어지는 수 이므로
  • 1과 자신 이외의 수로 나누어 떨어지면 소수가 아니라고 판정

for(int i=2; i<n; i++)
	if(n%i==0) return false;
return true;

=> 이 첫 번째 로직은 결국 2중 loop를 돌게되는 것이고, 문제 조건상 200,000이 입력된다면 제한시간인 1초안에 결과를 내놓을 수 없어 시간 초과가 나왔다.

따라서 나는 문제의 제목대로 [에라토스테네스의 체]에 대해 구글링을 하였다.
이에 대한 링크를 아래 첨부하겠다.
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

[해결책]
2. 두 번째 로직
: 에라토스테네스의 체

• 2부터 입력한 수 까지의 모든 자연수를 가진 배열을 초기화 한 후
• 2부터 시작하여 (어차피 2는 소수니까) 소수 count한 후
• 2를포함한 2의 모든 배수를 배열에서 지운다 (나의 경우는 0 대입)
• 이후 배열에서 2다음으로 0이 아닌 3에 대하여 같은 과정 반복

• 즉 3도 어차피 소수니까 소수 count한 후
• 3을 포함한 모든 3의 배수를 배열에서 지운다.
• 이후 배열에서 3다음으로 0이 아닌 수는 5가 나오고 같은 과정을 반복한다
  (4는 2의 배수이므로 지워졌음)
  (즉 이 알고리즘을 진행하다 보면, 0이아닌 다음 수는 항상 소수일 수 밖에 없는듯)
• 위 과정을 반복하면서 소수 count를 하면 -> 결과적으로 2부터 입력한 수 까지의 소수들을 모두 [빠르게] count할 수 있다.
  => 어떻게 이 알고리즘으로 소수를 판정할 수 있는지 보다는,
  이런 알고리즘도 있다는것을 인지하고 , 다음에도 사용할 수 있도록 하는것이 중요할 것 같다.

import java.util.Scanner;

public class Main {


    public static void removeElem(int[] arr, int n){

        for(int i = n; i<arr.length; i+=n){
            arr[i] = 0;
        }
    }

    public static void solution(int N) {


        //0부터 입력한 수 N까지를 1차원 배열에 초기화
        int[] arr = new int[N+1];
        for(int i=0; i<arr.length; i++)
            arr[i] = i;


        int cnt = 0;

        //이후 초기화된 배열에서 , [에라토스테네스의 체] 알고리즘을 써서 소수들 만을 걸러냄
        for(int i = 2; i<=N; i++){
            if(arr[i] != 0) {
                cnt++;
                removeElem(arr, i);
            }
            else
                continue;
        }


        for(int i=2; i<=N; i++){
            if(arr[i] != 0) cnt++;
        }

        System.out.println(cnt);


    }


    public static void main(String[] args) {
        //0. Scanner 준비
        Scanner sc = new Scanner(System.in);

        //1. N 입력받기
        int N = sc.nextInt();

        //2. solution() 에 N을 인자로 넘기면서, [에라토스테네스의 체] 알고리즘을 써서 소수의 개수를 구한다
        solution(N);
    }
}