소수 판별 알고리즘 정리 (시간복잡도 O(√n))

1. 소수란?

소수는 1과 자기 자신만 약수로 가지는 자연수이다.
예: 2, 3, 5, 7, 11, 13, 17, 19 …

---

2. 기본 소수 판별 로직

가장 단순한 방법은 2부터 n-1까지 나눠보는 것이다.

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

이 방식의 시간복잡도는 O(n) 이다.

---

3. √n까지만 확인해도 되는 이유

n이 소수가 아니라면
n = a × b인 두 자연수 a, b가 존재한다.

이때 a와 b가 모두 √n보다 크면
a × b > n이 되므로 모순이다.

→ 따라서 약수쌍 중 하나는 반드시 √n 이하
→ 즉, 2부터 √n까지만 나눠보면 충분

---

4. 개선된 소수 판별 코드 (O(√n))

boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

---

5. 예제: A 이상 B 이하 소수들의 합 구하기

int sumOfPrimes(int A, int B) {
    int sum = 0;
    for (int i = A; i <= B; i++) {
        if (isPrime(i)) sum += i;
    }
    return sum;
}

---

6. 시간복잡도 정리

• 소수 판별 1회: O(√n)
• 전체 합 계산: O((B - A + 1) × √B)
  (최악의 경우 B만큼 반복, 각 수마다 √B까지 확인)

---

제목 추천

소수 판별 알고리즘, 왜 √n까지만 보면 될까? (시간복잡도까지)

---