99클럽 코테 스터디 1일차 TIL + 소수 구하기

✅ 오늘의 학습 키워드

소수 구하기 (백준 문제) 

 

✅ 공부한 내용

소수(Prime Number)란?

 1과 자기 자신을 제외하고 나누어 떨어지는 약수가 없는 자연수

 

✅ 오늘의 회고

소수 판별 문제에서 단순 구현 시 O(N²) 시간복잡도가 나와 시간초과 발생

• 처음 작성한 코드:

bool isPrime(int n) {
    if (n < 2)
        return false;

    for (int i = 2; i < n; i++) { // 이 부분이 문제가 있음
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

• 제곱근까지만 검사하는 방식으로 개선:

bool isPrime(int n) {
    if (n < 2)
        return false;

    for (int i = 2; i * i <= n; i++) { // 제곱근으로 최적화
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

• 시간복잡도가 O(N²)에서 O(N√N)으로 개선됨

 

✅ 전체 코드

#include <iostream>

using namespace std;

bool isPrime(int n) {
    if (n < 2) 
        return false;

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

int main() {

    int M, N;
    int cnt;

    cin >> M >> N;

    for (int i = M; i <= N; i++) {
        if (isPrime(i)) {
            cout << i << '\n';
        }
    }

    return 0;
}

 

✅ 새롭게 알게 된 점

• 소수 판별 시 제곱근까지만 검사해도 충분한 이유: N = a×b 형태일 때 a와 b 중 하나는 반드시 √N 이하
• 문제의 제한 조건(N의 크기)을 보고 적절한 알고리즘을 선택하는 방법
• N ≤ 1,000,000인 경우 O(N²)는 시간초과, O(N√N) 또는 O(N log log N) 알고리즘이 필요

 

✅ 내일 학습할 것

• 시간복잡도를 개선하기 위해 에라토스테네스의 체 구현 방법 심화 → O(N log log N)으로