[코드트리] 소수2 - 자바(Java)

문제

https://www.codetree.ai/problems/prime-number-2?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

정수 n이 입력되었을 때, n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하세요.

 

입력 예시

100

 

출력 예시

25

 

 

코드

첫 번째 줄에 정수 n이 주어집니다.

• 0 ≤ n ≤ 10^5

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int count = 0;

        // 2부터 n까지 순회
        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) { // 소수인 경우 count 증가
                count++;
            }
        }

        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
    }

    // 소수 판별하기
    private static boolean isPrime(int num) {
        // 2부터 num의 제곱근까지 순회
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) { // num이 i로 나누어 떨어지는 경우 소수X
                return false;
            }
        }
        return true;
    }
}