[자료구조] 수학 - 소수(Prime Number) with Python

소수란? (Prime Number)

소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어 떨어지는 자연수이다.
8은 1, 2, 4, 8로 나누어 떨어지기 때문에 소수가 아니다.
7은 1과 자기자신인 7을 제외하고는 나누어 떨어지지 않으므로 소수이다.

📌 소수 판별의 기본적인 알고리즘

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

print(is_prime_number(8))
print(is_prime_number(7))

# False
# True

소수의 판별: 기본적인 알고리즘 성능 분석

• 2부터 x-1까지의 모든 자연수에 대해서 연산을 수행
  • 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(x)이다.

약수의 성질

• 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 것을 알 수 있다.
  • 예를 들어 16의 약수는 1, 2, 4, 8, 16이다.
  • 이때 2x8=16은 8x2=16과 대칭이다.
• 따라서 우리는 특정한 자연수의 모든 약수를 찾을 때 가운데 약수까지만 확인하면 된다.
  • 예를 들어 16이 2로 나누어 떨어진다는 것은 8로도 나누어 떨어진다는 것을 의미한다.

📌 소수 판별의 개선된 알고리즘

import math

def isPrime(x):
		for i in range(2, int(math.sqrt(x))+1):
				if x%i == 0:
						return False
				return True

print(isPrime(8))
print(isPrime(7))

# False
# True

📌 소수 판별 : 개선된 알고리즘 성능 분석

• 2부터 x의 제곱근까지의 모든 자연수에 대해서 연산을 수행해야 한다.
  • 시간 복잡도
  

📌 다수의 소수 판별

• 하나의 수에 대해서 소수인지 아닌지 판별하기 위해서는 기본 소수 알고리즘 사용
• 특정한 수의 범위 안에 존재하는 모든 소수를 판별하기 위해서는 에라토스테네스 체 알고리즘 사용

📌 에라토스테네스의 체

• 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법
• 다수의 자연수에 대해서 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다.
• 에라토스테네스의 체는 x보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.
• 에라토스테네스의 체 알고리즘의 구체적인 동작 과정은 다음과 같다.

1. 1은 제거
2. 2부터 x까지의 모든 자연수를 나열
3. 지워지지 않은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
4. 남은 수 중에서 i의 배수를 모두 제거 (i는 제거하지 않는다)
5. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복

📌 에라토스테네스의 체 알고리즘 동작 예시

📌 에라토스테네스의 체 구현

import math

n = 1000
array = [True for i in range(n+1)]

for i in range(2, int(math.sqrt(n))+1):
		if array[i] == True:
				j = 2
				while i*j <= n:
						array[i*j] = False
						j += 1

for i in range(2, n+1):
		if array[i]:
				print(i, end='')

📌 에라토스테네스의 체 알고리즘 성능 분석

• 에라토스테네스의 체 알고리즘의 시간 복잡도는 사실상 선형 시간에 가까울 정도로 매우 빠르다.
  • 시간 복잡도는 O(NloglogN) 이다.
• 에라토스테네스의 체 알고리즘은 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있다.
  • 하지만 각 자연수에 대해서 소수 여부를 저장해야 하므로 메모리가 많이 필요하다.

Reference

https://www.youtube.com/watch?v=CyINCmJPjfM&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=37
https://www.youtube.com/watch?v=9rLFFKmKzno&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=38
https://wikidocs.net/21638