설명

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

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

코드

public class PrimeNumber {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input = in.nextInt();
        solution(input);
    }

    public static void solution(int input){
        int[] arr = new int[input+1];   //배열을 검사할때 배열과 index값을 맞추기 위해
        int count = 0;
        for(int i=2; i<=input; i++){
            if(arr[i]==0){  //arr[i] == 0일 경우 해당 index는 소수이므로 카운트
                count++;
                for(int j=i; j<=input; j+=i){  //해당 수의 배수들은 모두 체크
                    arr[j] = 1;
                }
            }
        }
        System.out.println(count);
    }
}

지금까지 소수를 구하면서 수 많은 에라토스테네스 체를 구현하는 코드를 봐왔지만 나는 이게 가장 쉽게 느껴지고 가독성도 가장 좋은 코드인거 같다.

에라토스테네스 체로 푸는 문제는 해당 알고리즘을 기억하고 풀자!

참고!
소수 : 에라토스테네스 체
최대 공약수 : 유클리드 호제법