# 소수 판별 알고리즘

일반적인 소수 판별에는  '2. 2부터 n 제곱근까지 숫자들로만 나눠서 확인' 정도만 쓴다.

범위 내의 소수를 모두 구하는 경우에는 '3. 에라토스테네스의 체'가 효율적이다.

### 판별 알고리즘

#### 1. 하나씩 전부 나눠보기

2부터 목표 숫자-1까지 전부 나눠보고 안 나눠지면 소수

```python
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
```

#### 2. 2부터 n 제곱근까지 숫자들로만 나눠서 확인

16을 예로 들면, 제곱근인 4까지만 확인해보면 4 초과부터는 확인할 필요 없다.

```python
import math

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
```

#### 3. 에라토스테네스의 체

아래에서 훑는데 각 수의 배수도 날림.

한 개의 소수를 구할 때 적합한 방법이라기보단

범위 내의 모든 소수를 구할 때 적합.

```python
n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)
```

코드 출처 : <https://wikidocs.net/21638>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined/undefined-10.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.