[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 primelis...