JAVA)1978번 소수 판별 문제

소수를 판별하기 위해서는 그 수가 소인수(자연수를 나누어 떨어뜨리는 약수 중 소수인 수)를 갖는 지 확인해야한다.

어떤 수가 소수가 아니라면, 그 수(N)는 N = a*b (a, b는 소수)꼴로 나타낼 수 있다.

이 때, a>b 라고 하면, a는 언제나 루트(N)보다 작은 값을 가지고, b는 루트(N)보다 큰 값을 가진다.

그러므로 루트(N)보다 작은 수에 대해서만 N이 나누어떨어지는지 확인하면 N이 소수인지의 여부를 파악할 수 있다.

반복문은 루트(N)번 반복되며 시간 복잡도는 O(루트(N))이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        int num_of_prime = 0;
        for (int i=0;i<cnt;i++) {
            int num = sc.nextInt();
            if (checkPrime(num)) { // 소수 맞으면 조건문 들어감
                num_of_prime++; // 소수 개수 1개 추가
            }
        }
        System.out.println(num_of_prime);
    }

    public static boolean checkPrime(int num) {
        if (num < 2) { // 2보다 작은 소수는 없다.
            return false;
        }
        // i는 num이 소수인지 판별하기 위해 나누어주는 수(2부터 나누어주면 됨)
        for (int i=2;i*i<=num;i++) { //java에서 int의 범위는 -2147483648 ~ 2147483647 (num의 최대 입력인 1000을 충분히 수용가능)
            if (num%i == 0) { // 나누어 떨어지는 수가 존재한다면
                return false; // 소수가 아니다.
            }
        }
        return true; // 위 조건들을 모두 통과한다면 소수 맞음
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1978