[백준] 1978번 소수 찾기 - Java, 자바

문제

https://www.acmicpc.net/problem/1978

코드

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

import static java.lang.Math.sqrt;

// 1978번 소수 찾기
public class boj_4_1978 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine(); // n 쓰지 않음

        int count = 0;

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        while (st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            if (isPrime(num)) count++;
        }

        System.out.println(count);
    }

    public static boolean isPrime(int num) {
        if (num == 1) return false;

        for (int i = 2; i <= sqrt(num); i++) {
            if (num % i == 0) return false;
        }

        return true;
    }
}

풀이

소수란 1과 자기 자신만을 약수로 갖는 수이다.
소수인지 판별하는 방법은 2부터 판별하려는 수 직전까지 나누어 떨어지는 수가 없다면 소수이고 나누어 떨어지는 수가 있다면 소수가 아니다.

방법1) 정석적인 방법

1은 소수가 아니므로 예외적으로 처리해준다.

    public static boolean isPrime(int num) {
        if (num == 1) return false; 

        for (int i = 2; i < num; i++) {
            if (num % i == 0) return false;
        }

        return true;
    }

방법2) 제곱근을 이용한 방법 -> 사용!

Number을 A x B 의 합성수 (Number = A x B) 라고 볼 때 아래와 같이 부등식을 세울 수 있다.
1 <= A, B < Number

여기서 만약 A와 B가 Number의 제곱근보다 커지면 위 부등식에 모순이 생긴다.

따라서 합성수 Number = A x B 에서 A와 B 중 적어도 하나는 Number의 제곱근보다 작거나 같다.
따라서 소수를 판별할 때 굳이 Number -1 까지가 아닌 Number의 제곱근까지만 검사하면 된다.

    public static boolean isPrime(int num) {
        if (num == 1) return false;

        for (int i = 2; i <= sqrt(num); i++) {
            if (num % i == 0) return false;
        }

        return true;
    }

참고
https://st-lab.tistory.com/80