소수 찾기 알고리즘

주어진 범위에서 소수 찾기는 코딩 공부를 하다보면 여러번 마주치게 되는데 관련된 내용을 정리해보려 한다.

 

소수의 정의 (Prime number)

1과 자신만으로 나누어지는 정수(1은 소수가 아니다.)

 

1)

소수인지 확인하는 함수 구현

 

주어진 정수 n이 소수인지 확인하기 위해서는 2부터 제곱근n 까지의 수로 n이 나누어지는 수가 있는지를 확인하면 된다. 

정수 n의 최대 약수는 제곱근n이므로 제곱근n까지만 확인하면 된다. int로 정수화를 해주고 range함수에서 마지막은 포함을 안 하므로 +1해주었다. 

def isPrimge(n):
    for i in range(2, int(n**(1/2))+1):
        if n % i == 0:
            return False
    else:
        return True

 

2)

n까지의 정수 중 소수의 개수를 반환하라

 

2를 제외하면 모든 소수는 홀수이므로 2를 제외한 짝수는 애초에 고려할 필요가 없다. 

def solution(n):
    answer = 0
    
    lst = list(range(2,n+1))
    lst = [k for k in lst if k%2 == 1 ]
    lst.append(2)
    
    for i in lst:
        if isPrimge(i):
            answer += 1
    
    return answer

 

3) 

에라토스테네스의 체

 

소수를 찾으면 그 소수를 추가하고 찾은 소수 자신을 제외한 배수를 구간에서 모두 지워가면서 범위 내 소수를 찾는다.  

 

120까지의 소수를 전부 찾아라 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(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 [i for i in range(2, n) if sieve[i] == True]
    
prime_list(20)
# [2, 3, 5, 7, 11, 13, 17, 19]

max(prime_list(1000000))
# 999983