소수 판별

✅ 소수 판별

1️⃣ O(n)으로 구현하기

소수(prime number)란, 1과 자기 자신 외의 수로 나누어지지 않는 수를 말한다. 즉, 약수(divisor)가 1과 자기 자신밖에 없는 수가 소수인 것이다. 이러한 소수의 특성을 이용해서 입력한 숫자가 소수인지 판별하는 Python3 코드를 작성해보면 다음과 같다.

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

위의 코드는 입력 숫자 n 을 2 부터 n-1 까지 차례대로 나누어서 만약 나누어진다면 False(소수가 아님), 나누어지면 True(소수임)를 반환하여 소수인지 아닌지 판별한다. 시간 복잡도 O(n) 으로, 가장 기초적인 방법임에도 나쁘지 않은 효율을 갖고 있다고 말할 수 있겠다. 하지만, n이 커지면 연산량이 그만큼 많아지게 된다.

2️⃣ O($\sqrt{n}$)으로 구현하기

연산량을 좀 더 줄여보자. 약수의 특성을 활용하면 어떨까? 어떤 수의 약수, 예를 들어 16의 약수들을 나열한다고 생각해보자. 나열하면 다음과 같다.

16의 약수
1, 2, 4, 8, 16

나열한 수들을 자세히 보면 중앙값을 기준으로 대칭을 이루고 있는 것을 알 수 있다. 또한 중앙값 이후의 약수들은 중앙값 이전의 약수들로 나눌 수 있다. 그렇다면 중앙값 즉, 소수인지 판별하고 싶은 어떤 수의 제곱근 보다 작은 수들로 나누어진다면, 제곱근 보다 큰 수들로 나누어 보지 않아도 소수가 아님을 알 수 있다. 이 방식으로 코드를 설계하게 되면 시간 복잡도 O($\sqrt{n}$) 으로, 이전 보다 효율성을 좀 더 챙길 수 있게 된다. Python3로 작성해보면 다음과 같다.

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

✅ 특정 구간에서 소수 찾기

지금까지는 어떤 수가 입력되었을 때, 해당 수가 소수인지 아닌지 판별하는 문제를 다루어보았다. 위의 코드를 이용해서 특정 구간에서의 모든 소수를 찾는 코드를 작성해보면 다음과 같다.

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

def findPrimeNumbers(start, end):
	result = []
	for i in range(start, end+1):
		if checkPrimeNumber(i):
			result.append(i)
	return result

findPrimeNumbers(10, 100)

에라토스테네스의 체

위의 코드는 시간복잡도 O($n^2$) 에 가까운 연산을 수행한다. 조금 더 빠른 코드를 작성해보고 싶다면 에라토스테네스의 체를 적용하면 된다. 에라토스테네스의 체 알고리즘은 다음과 같이 작동한다.

그림 출처: 위키백과

💡 에라토스테네스의 체 규칙
1️⃣ 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2️⃣ 2부터 시작하여 소수의 배수들을 차례로 지워 나간다. 이 때 자기 자신은 지우지 않으며, 이미 지워진 수는 넘어간다.
3️⃣ 더이상 지울 숫자가 없을 때까지 2번을 반복한다.
4️⃣ 3번 이후 남아있는 숫자가 소수가 된다.

에라토스테네스의 체를 사용하면 소수 찾는 문제를 시간 복잡도 O($NloglogN$) 으로 구현할 수 있다. 굉장히 빠른 속도로 연산할 수 있지만, 입력 수만큼의 데이터 공간을 만들어야 하기 때문에 너무 큰 수에 대해서는 메모리를 많이 쓴다는 단점이 있다. 하지만 컴퓨터 메모리가 부족할 정도로 큰 범위의 소수 찾기 문제는 흔치 않으므로 편하게 쓰도록 하자. 해당 알고리즘을 적용한 코드는 다음과 같다.

def SieveOfEratosthenes(n):
	isPrime = [True] * (n+1)
	for i in range(2, int(n**0.5)+1):
		j = 2
		while i*j <= n:
			isPrime[i*j] = False
			j += 1
	return isPrime

def findPrimeNumbers(start, end):
	isPrime = SieveOfEratosthenes(end)
	result = []
	for i in range(start, end):
		if isPrime[i]:
			result.append(i)
	return result

findPrimeNumbers(10, 100)