소수 찾기 알고리즘

소수(prime number)
: 1보다 큰 자연수 중, 1과 자기 자신 외에는 나누어지지 않는 수

방법1 : 2부터 n-1까지 나눠보기

• 소수의 정의를 그대로 활용한 방법
• 1과 자기 자신을 제외한 모든 수로 한 번씩 나눠봄
• 시간복잡도 O(n)

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

방법2 : 2부터 n의 제곱근까지 나눠보기

• 소수와 관련된 정리 이용 → N의 제곱근보다 작은 수로 나누어 떨어지지 않으면 N은 소수이다.
  
• 2부터 n-1까지 나눔으로써 가능

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

방법3 : 에라토스테네스의 체

• 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 이용
  1. 2부터 N까지의 수를 포함한 배열을 만든다.
  2. 배열의 숫자 중에서 가장 작은 수를 x라 하면 x의 배수는 모두 합성수이므로 배열에서 x를 제외한 x의 배수를 모두 제거한다.
  3. x 다음으로 작은 수를 가지고 2의 과정을 반복한다.
  4. 더이상 반복할 수 없을 때까지 2, 3번의 과정을 반복한 다음 남은 숫자는 모두 소수이다.

n = 1000
array = [True] * (n+1)
arr[0] = False
arr[1] = False

def is_primenumber(n, array):
	for x in range(2, int(n**0.5) + 1):
		if array[x] == True:
			step = 2
			while x * step <= n:
				array[x*step] = False
				step += 1
	return array