[Python][Algorithm] 소수 판별(에라토스테네스의 체)

소수 판별

소수의 정의를 이용한 단순 소수 판별은 파이썬으로 다음과 같다.

1 2 3 4 5

def isPrime(num): #num이 소수인지 여부 확인 for i in range(2,num) : # 2부터 num-1 까지의 수 중 num을 나눌 수 있는 수 존재 여부 확인 if num % i == 0 : return False return True

위와 같은 경우 시간복잡도는 O(n)이 된다.

하지만 소수의 경우 대칭을 이루기 때문에 (ex) 8 = 2 * 4, 8 = 4 * 2) i의 range는 사실 (2, num)이 아니라 (2, num//2)면 된다. 이렇게 되면 O(n^(1/2))의 시간 복잡도를 가진다.

(추가적으로, 사실 2가 아니라 num이 갖는 소인수중 가장 작은 값으로 나누면 된다. 이렇게 되면 시간 복잡도가 더 작아진다.)

이와 다르게, 일정 범위 내의 소수 집합을 찾기 위해서는 에라토스 테네스의 체를 활용하면 빠른 시간안에 연산이 가능하다.

에라토스 테네스의 체

우선, 범위 내에 전체 배열을 생성한 뒤, 특정 소수의 배수들을 제거해 나가는 방식으로 진행하여 남은 수들의 집합을 구하면 범위 내의 소수 집합이 된다. 이 때, 특정 수들은 지우지 않고 배수들만 지워나간다. 파이썬 코드는 아래와 같다.

1 2 3 4 5 6 7 8 9

def primeSieve(num): # 2부터 num 까지의 수 중 소수 집합 구하기 primelist = [True] * (num+1) # 0부터 num까지 초기화 sqrtnum = int(num**(1/2)) # 소수는 대칭을 이루므로 square root까지만 계산 for i in range(2, sqrtnum+1): # 2부터 sqrt 까지 체크 if primelist[i] == True : # i가 소수라면 for j in range(i+i, num+1, i): # i의 배수들 삭제 primelist[j] = False return [i for i in range(2, num+1) if primelist[i]==True] # 값이 True인 것만 출력