소수 판별

19 Apr 2023 in Algorithm on Java, Coding, Test

문제

설명

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

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

입력

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

출력

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

예시 입력 1

20

예시 출력 1

8

해결방법

• 소수 : 자기자신을 제외하고 나누어지는 수가 없는 수.
  • 자기 자신보다 낮은 수들로 나누었을 때, 전부 나누어 떨어지지 않아야 함.
  • 자기 자신의 제곱근 보다 낮은 수들로 나누었을 때, 떨어지지 않아야 함.

코드

import java.util.*;

class Main {
    public int solution(int n) {
        int cnt = 0;
        int[] ch = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (ch[i] == 0) {
                cnt++;
                // 자기 자신의 제곱 위치에 체크 1을 넣음으로써 나누어 떨어지는 경우를 전부
                // 체크하여 1로 만든것 -> 따라서 해당 위치의 수는 소수가 아니므로 체크하지 않음.
                for (int j = i; j <= n; j = j + i) ch[j] = 1;
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        Main.Main T = new Main.Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        System.out.println(T.solution(n));
    }
}