[백준 문제 풀이] 1978번 소수 찾기

Junu Kim·2025년 7월 15일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

18/46

[1978] 소수 찾기

난이도: ★★☆☆☆ • solved on: 2025-07-15

문제 요약

문제 유형: 수학, 구현
요구사항: N개의 자연수 리스트에서 소수의 개수를 구해야 한다.

사용 개념

자료구조
- 배열(Array)
알고리즘/기법
- 반복문
- 소수 판별(제곱근 이용)
- 에라토스테네스의 체(Sieve of Eratosthenes)
핵심 키워드
- 제곱근(sqrt), 체(sieve), boolean 배열

풀이 아이디어 및 코드

방법 1 : 제곱근 판별법

입력받은 각 수 num에 대해:

num == 1 → 소수가 아님 (카운트에서 제외)

num == 2 → 소수

그 외: 2부터 √num까지 나누어 떨어지는 수(j)가 있으면 소수가 아님 (카운트 제외), 없으면 소수

카운트 결과 출력

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        int result = n;
        String[] arr = br.readLine().split(" ");
        for(int i=0;i<n;i++){
            int num = Integer.valueOf(arr[i]);
            if(num == 1){
                result -= 1;
                continue;
            }
            if(num == 2){
                continue;
            }
            for(int j=2;j<=Math.sqrt(num);j++){
                if(num%j==0){
                    result -= 1;
                    break;
                }
            }
        }
        System.out.print(result);
    }
}

방법 2 : 에라토스테네스의 체

입력값 중 최대값 M을 구함

크기 M+1인 boolean 배열 sieve를 생성하고, 2부터 M까지를 true로 초기화 (0과 1은 false)

i = 2부터 √M까지 순회하며 sieve[i] == true일 때 그 배수들을 false로 마킹

입력 배열을 순회하며 sieve[num] == true인 경우 소수 카운트

결과 출력

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));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] nums = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, nums[i]);
        }
        boolean[] sieve = new boolean[max + 1];
        Arrays.fill(sieve, true);
        sieve[0] = sieve[1] = false;
        for (int i = 2; i <= Math.sqrt(max); i++) {
            if (sieve[i]) {
                for (int j = i * i; j <= max; j += i) {
                    sieve[j] = false;
                }
            }
        }
        int count = 0;
        for (int num : nums) {
            if (sieve[num]) count++;
        }
        System.out.print(count);
    }
}

시간·공간 복잡도

방법 1

시간 복잡도: O(N × √M)

공간 복잡도: O(N)

방법 2

시간 복잡도: O(M log log M + N)

공간 복잡도: O(M)

어려웠던 점

방법 1: 반복문 제어 변수와 결과 변수의 이름이 혼동되어 의도치 않게 값이 변경되는 의도치 않은 결과가 발생해서 처음에는 오답을 제출했었다.
방법 2: 최대값 M 계산 후 boolean 배열 초기화 및 메모리 사용량 고려가 필요했다.

배운 점 및 팁

에라토스테네스의 체로 다수의 수에 대한 소수 판별을 전처리 방식으로 빠르게 수행 가능하다.
Math.sqrt() 결과는 루프 시작 전에 변수에 저장하면 반복 시 계산 오버헤드가 감소한다.
변수명을 명확히 구분해 의도치 않은 값 변경을 방지하자 (for문 내부의 변수 특히 조심)
for문 내부에서 루프 한계값을 변경하면 발생하는 문제

: Java의 for(int i = 0; i < n; i++) 구조에서, 본문({ … }) 안에서 n을 변경하면 루프 조건(i < n)이 매 반복마다 재평가되기 때문에 의도치 않게 반복 횟수가 달라진다.

1. for문의 동작 원리
```
// for문
for (초기화; 조건; 증감식) {
    // 본문
}
// 내부적으로는 아래와 같다
초기화;
while (조건) {
    // 본문
    증감식;
}
```
- 조건 검사(i < n) 는 매 반복 직전에 실행한다.
- 본문에서 n을 줄이면, 다음 반복부터 바뀐 값이 조건에 반영된다
2. 실제 예시
```
int n = 5;
for (int i = 0; i < n; i++) {
    n--;  
    System.out.printf("i=%d, n=%d%n", i, n);
}
```
반복 i (초기값) n (검사 전) 본문 실행 후 n 증감식 후 i
1 0 5 4 1
2 1 4 3 2
3 2 3 2 3
4 3 2 — (조건 불통과) — (종료)

→ 4번째 반복부터 i < n이 거짓이 되어 루프가 종료된다.

해결 방법 및 팁
1. 루프 제어 변수와 결과 변수 분리 (방법1에서 사용된 방법)
```
int size = Integer.parseInt(...);   // 반복 횟수 고정
int primeCount = size;              // 결과 저장용
for (int i = 0; i < size; i++) {
    // 본문에서 size를 변경해도 반복 횟수에는 영향 없음
}
```
2. 상수로 선언 (with final)
```
final int MAX = size;
for (int i = 0; i < MAX; i++) { … }  ```
```
3. 반복 범위를 동적으로 변경해야 할 때
  - while + break 구조를 사용하거나
  - 별도의 카운터 변수를 두어 관리