[Python] 소수 찾기 알고리즘

소수란?

1보다 큰 자연수 중, 1과 자기 자신 외에는 나누어지지 않는 수

 

누가 알고리즘 문제를 만드는지 모르겠으나 이 사람들 소수 찾기에 진심이다. 학교에서 수학 배울 때 빼고 단 한 번도 신경 쓰지 않았던 소수, PS 하다가 소수 문제가 하도 많이 나와, 한 번 정리해야겠다 싶어 정리한다. 

소수 찾기 알고리즘

소수 찾는 방법은 여러 가지가 있다. 소수인지 판별이 필요한 수를 n이라고 하겠다.

1. 숫자 n 나누기

2부터 n-1까지 나누기

def isPrime(n):
    for i in range(2, n):
        if n % i == 0:
            return False  
    return True

n-1까지, n이 1과 자기 자신 외의 수로 나누어지는지 판단하는 알고리즘이다. 만약 나누어진다면 바로 false를 리턴한다. n-1까지 걸리지 않는다면 True가 리턴된다. 가장 간단하고, 기초적이지만 오래 걸린다. 2부터 n-1까지의 수 모두를 확인하기 때문에, 시간 복잡도가 O(n)이다.

 

n/2까지 나누기

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

n의 모든 약수는 n/2보다 작다. 고로 2부터 n-1까지 확인할 필요가 없다는 뜻이다. 위 알고리즘보단 확인해야 할 조건이 반으로 줄었지만 여전히 시간 복잡도가 O(n)이기 때문에 느리다. 

 

n의 제곱근까지 나누기

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

n의 제곱근을 기준으로, 제곱근보다 작은 수들 중에 약수가 없다면, 제곱근보다 큰 수들은 n의 약수가 아니다. 예를 들어 n이 101이라면, √101+1까지의 수만 약수인지 확인해보면 된다. 만약 n/2 알고리즘을 쓰면 101//2+1 = 51, 즉 2~51까지 50번을 확인해야 하지만, n의 제곱근까지만 확인하면 √101+1 = 11, 즉 2~11까지 총 10번만 하면 된다. 그래서 시간 복잡도는 O(√n)으로, 1번의 방법들 중 제일 빠른 방법이다.

 

지금까진 하나의 숫자가 들어왔을 때 그 수가 소수인지 아닌지 판별하는 방법을 알아봤다. 그러나 판별해야 하는 수가 여러 개라면? 100개의 수를 판별해야 한다면 위의 알고리즘을 100번 반복해야 하는데 이게 가장 효과적인 방법일까? 이럴 때 바로 에라토스테네스의 체를 사용하는 것이다.

2. 에라토스테네스의 체

def primeList(n):
    # n을 포함시키기 위함
    n += 1
    # [False(0), False(1), True(2), True(3), True(4) ... True(n)]
    sieve = [False, False] + [True] * (n)
    end = int(n ** 0.5) + 1
    for i in range(2, end):
        if sieve[i] == True:
            for j in range(i + i, n, i):
                sieve[j] = False
                
    return [i for i in range(n) if sieve[i] == True]

 

sieve라는 0~n까지의 숫자가 소수라면 True, 아니면 False 값을 담고 있는 배열을 생성한다. 그리고 최대 약수인 √n을 종료 값으로 설정한 뒤, 만약 sieve[i]값이 참이라면(=소수라면) 그 값의 배수들을 모두 거짓(=소수가 아님)으로 바꾼다. 그리고 마지막에는 sieve의 값에 따라, 참이라면 return 배열에 i를 추가하는 방식으로 사용할 수 있다. 

---

참고:

 

1. https://myjamong.tistory.com/139

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽

2. https://seongonion.tistory.com/43

소수판별 알고리즘 - 파이썬 (Python)

3. https://wikidocs.net/21638

2. 소수 구하기 - 에라토스테네스의 체