[BOJ] 1978 소수 찾기 (Java)

# 출처 : https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

---

# 문제

소수가 몇 개인지 찾아서 출력하는 프로그램

---

# 풀이

소수를 판별하는 가장 단순한 방법은 2~n-1까지 모든 수를 순회하면서 n의 약수가 있는지 확인하는 것.

약수가 존재하지 않는다면, 소수이다.

 

여기서 포인트는 1과 자기자신을 제외한 약수가 존재하는지 확인하기 위해서는 제곱근(루트)까지만 확인하면 된다.

왜냐하면 약수들은 대칭적으로 짝을 이루기 때문이다.

 

예를 들어,

i ) n=9일때

'9의 제곱근 = √9 = 3' 이기 때문에 2에서 3까지 수 중에서 9의 약수인지 확인하면 된다.

3은 9의 약수이기 때문에 소수가 아니다.

 

한번더 예를 들어,

ii ) n=8일때

'18의 제곱근 = 3√2 ' 이므로 대략 4.xxxx 으로 되겠다. (※참고. √2 = 1.4xx, √3=1.7xx)

(제곱근 값 쉽게 유추하는 법: √16 < √18 < √25 = 4 < √18 < 5 이므로 4.xx값을 가진다는 것을 알 수 있다.(제곱 수를 루트에 넣을것!))

그렇다면 18은 2에서 4까지 수 중에서 18의 약수인지 확인하면 된다.

2와 3은 18의 약수이기 때문에 소수가 아니다.

 

마지막 예를 들어,

iii ) n=13일때

'13의 제곱근 = √13' 이므로 대략 3.xx 값을 갖는다. (√9 < √13 < √16 = 3 < √13 < 4)

13은 2와 3이 13의 약수가 아니기 때문에 소수다

---

# 코드

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        int count=0;
        for(int i=0; i<N; i++){
            count += primeIdentification(s.nextInt()) ? 1 : 0; // 소수라면 true 이므로 카운팅
        }
        System.out.println(count);
    }

    public static boolean primeIdentification(int num){
        if(num==1) return false;
        for(int i=2; i*i<=num; i++){ // 제곱근까지만 확인하기 위해서
            if(num % i == 0) return false; // 하나라도 약수가 된다면, 바로 for문 종료
        }
        return true;
    }
 }