소수 판별 알고리즘

• 소수 : 1과 자기 자신 외에는 어떤 수로도 나누어 떨어지지 않는 수

특정 수 N이 소수인지 판별법

💡 Idea 1

• 1과 자기 자신 외에는 나누어 떨어지지 않는 소수의 특성 활용

1. 2부터 N-1까지 수로 N을 나누어보고
2. 이 중 어떤 수에 의해 나누어 떨어지는지 확인
   ( 나누어 떨어지는 수가 있으면 소수가 아니다.)

• 시간복잡도 O(N)

🛠 Code

def is_prime_num(N):
    if N == 1:  # 1은 소수가 아니다.
        return False
    for i in range(2, N):
        if n % i == 0:
            return False  # 나누어 떨어지면 소수가 아니기 때문에 False
    return True  # 나누어 떨어지지 않으면 소수이기 때문에 True

💡 Idea 2

• N의 약수를 나열했을 때 가운데 수를 중시믕로 대칭되는 약수의 특성 활용
  - 중간값을 기준으로 반절만 검사하면 되기 때문에 연산 횟수를 반감시킬 수 있다.

1. 절반에 대해 앞에 Idea1 알고리즘을 사용

🛠 Code

def is_prime_number(N):
    for i in range(2, int(math.sqrt(N))+1):  # 반절만 확인
        if N % i == 0:
            return False
    return True

---

여러개의 수에 대한 소수 판별법: 에라토스테네스의 체

에라토스테네스의 체

💡 Idea
1. 2~N까지의 배열을 만든다
2. 해당 배열 내 가장 작은 수 i부터 시작, i의 배수를 지운다.
(i는 소수이므로 지우지 않는다.)
3. 범위 내에서 i 다음으로 작은 수의 배수를 지운다.
(이때 역시 i 다음으로 작은 수는 소수이므로 지우지 않는다.)
4. 더이상 반복할 수 없을때까지 위 과정을 반복한다.

🛠 Code

# n보다 작은 소수 리스트를 구하는 함수
# n보다 같거나 작은 소수 리스트를 구하기 위해서는 범위를 n 대신 (n+1)로 바꿔주면 된다.
def prime_list(n):
    # 체 초기화 : n개의요소에 True 설정
    sieve = [True] * n
    # n의 최대 약수가 sqtr(n) 이하이기 때문에
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:  # i가 소수인 경우
            for j in range(i+i, n, i):  # i 이후 i의 배수를 False 판정
                sieve[j] = False
    # 소수 목록 return
    return [i for i in range(2, n) if sieve[i] == True]