소수(에라토스체네스 체)

• 자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. 만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

public class Main {
    public static void main(String[] args) {

        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        System.out.println(T.solution(num));
    }
    

    public int solution(int num) {
        int[] arr = new int[num+1];
        int count = 0;

        for (int i = 2; i <= num; i++) {
            if (arr[i] == 0){
                count++;
                for (int j = i; j <= num; j=j+i) { 
                    arr[j] = 1;
                }
            }
        }
        return count;
    }
        
}

1. 인덱스 번호를 기준으로 소수 여부를 판단한다. 0과 1은 소수가 아니므로 인덱스 번호는 2부터 시작한다.

2. 인덱스를 체크하고 인덱스 번호의 배수들을 체크