99클럽 코테 스터디 1일차 TIL - 소수 구하기 (백준 1929번)

오늘의 학습 키워드

소수 판별, Math.sqrt(), 반복문, 시간 복잡도 O(√n)

---

공부한 내용 정리

오늘은 백준 1929번 문제인 “소수 구하기”를 풀었다.

두 수 M과 N이 주어졌을 때, M 이상 N 이하의 모든 소수를 출력하는 문제다.

소수 판별을 위해 isPrime() 함수를 직접 구현했고, √n까지만 나눠보는 방식으로 효율을 높였다.

Java의 Scanner를 활용해 입력을 받고, 반복문으로 범위를 순회하며 소수인 경우만 출력했다.

---

소스코드

import java.util.Scanner;

public class Main {

    // 소수 판별 함수
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        int sqrt = (int) Math.sqrt(n);
        for (int i = 2; i <= sqrt; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();

        for (int i = a; i <= b; i++) {
            if (isPrime(i)) {
                System.out.println(i);
            }
        }
    }
}

---

오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지

소수 판별을 처음부터 직접 구현하려다 보니 시간 복잡도가 걱정되었음.

반복문을 N까지 돌릴 필요 없이 √n까지만 보면 된다는 것을 떠올려 적용해봄.

• 어떻게 해결했는지

Math.sqrt()를 활용해 소수 판별 범위를 줄였고, 결과적으로 시간 초과 없이 통과할 수 있었음.

• 무엇을 새롭게 알았는지

소수를 판별할 때 굳이 N까지 확인하지 않아도 √n까지만 확인해도 충분하다는 점을 다시 한 번 명확히 이해함.

또, 문제 범위가 커질수록 효율적인 알고리즘(예: 에라토스테네스의 체)의 필요성도 느꼈음.

• 내일 학습할 것은 무엇인지

내일은 에라토스테네스의 체를 직접 구현해보며, 오늘 방식과의 성능 차이를 비교해볼 예정.

---