소수 찾기(수학, 정수론, 소수 판정)

문제

스크린샷 2023-11-27 오후 6 15 16

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int count = 0;

        while (st.hasMoreTokens()) {
            boolean isPrime = true;
            int num = Integer.parseInt(st.nextToken());

            if (num == 1) continue;

            for (int i = 2; i <= Math.sqrt(num); i++) {
                if (num % i == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) count++;
        }
        System.out.println(count);
    }
}

while 문으로 st의 값이 없을 때까지 루프를 돌리고, num이 1이면 계속 진행하고, for 문으로 2 부터 시작하여 Math.sqrt()를 활용해 제곱근까지 숫자로 나눌 수 있는지 확인한다.

여기서 num = 2인 경우는 자연스럽게 for문을 검사하지 않게 된다.

만약 나누어 떨어지지 않으면 소수로 간주하여 count++ 한다.

결과

스크린샷 2023-11-27 오후 8 46 50