[백준] 1978 소수 찾기 - Java

📌 문제 정보

• 출처: 문제 링크
• 난이도: ⭐ 
• 문제 유형: 소수
• 사용 언어: Java

---

🔍 문제 설명

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

주어진 수들 중 소수의 개수를 출력한다.

---

💡 풀이 노트

1. `if(num == 1) continue;`
   1. 숫자 `1`은 소수가 아니기 때문에, 아예 검사를 건너뛰도록 `continue`를 사용
   2. 소수는 정의상 2 이상의 자연수 중 약수가 1과 자기 자신뿐인 수
2. `boolean isPrime = true;`
   1. 각 수마다 처음엔 소수라고 가정하고 `true`로 설정
   2. 만약 나누어떨어지는 수가 발견되면 → `false`로 바꾸고 반복문 종료

   3. `for(int j = 2 ; j <= Math.sqrt(num) ; j++){`

1. 소수를 판별할 때 `Math.sqrt(num)`까지만 검사하는 이유

어떤 수 num이 소수가 아니라면,
반드시 `num = a × b`인 두 수가 존재.
이때 `a`와 `b`가 모두 `√num`보다 크다면 `a × b > num`이 되기 때문에
적어도 하나는 `√num` 이하의 수여야 함.

• `2부터 √num`까지 하나라도 나누어떨어지면 → 소수 아님
• 아무것도 안 나눠떨어지면 → 소

---

🚀 코드 (Java)

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int cnt = 0; // 소수 개수 카운트

        for(int i = 0 ; i < n ; i++){
            int num = Integer.parseInt(st.nextToken());
            boolean isPrime = true;

            if(num == 1)
                continue;

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

---

🖥 실행 결과

입력

4
1 3 5 7

 

출력

3

 

---

📌 깃허브 코드 저장소: https://github.com/glorypang/CodingTest