소수 목록 구하기와 에라토스테네스의 체

소수 목록 구하기

소수는 약수가 1과 자기 자신뿐인 수를 말한다.

그래서 소수는 2, 3, 5, 7 등이다.

4는 약수가 1, 2, 4라 소수가 아니다.

 

10까지 소수를 구하라는 문제가 있을 때, 가장 쉽게 떠오르는 방식은 소수의 정의대로 2부터 시작해서 자기 자신보다 작은 수까지 쭉 나눠보는 거다.

2는 소수

3은 2까지 나눠서 안 떨어지니 소수!

4는 2부터 나눠서, 2로 바로 나눠떨어지니 중지.

5는 2부터 4까지 나눠서 안 떨어지니 소수!

이렇게 구현하면? 코딩 테스트에서 시간초과로 떨어진다.

너무 오래 걸리니까.

이럴 때 검색이 필요하다. 소수 구하기를 검색하다보면 에라토스테네스의 체가 나온다.

 

에라토스테네스의 체란?

고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. (출처: 위키백과 에라토스테네세의 체)

에라토스테네스의 체 원리(출처: 위키백과)

120까지 소수를 구한다면, 모든 수가 소수라고 가정한 뒤에, 먼저 2가 소수니까, 2의 배수는 모두 제외, 그 다음 3으로 넘어가서 3도 소수, 3의 배수는 모두 제외하는 방식이다.

설명을 들으면 와! 하게 된다. 저렇게 간단하게 찾을 수 있다니! 그러니 이름이 남아 있게 된 것!

 

파이썬 구현 예

	def sieve_of_eratosthenes(number):
	prime_numbers = [True for _ in range(number + 1)]
	square_root = int(number ** 0.5)
	print(f'square_root: {square_root}')
	for i in range(2, square_root + 1):
	print()
	print(f'i: {i}')
	if prime_numbers[i]:
	for j in range(i + i, number + 1, i):
	print(f'j: {j}')
	prime_numbers[j] = False
	result = []
	for i in range(2, number + 1):
	if prime_numbers[i]:
	result.append(i)
	return result
	if __name__ == '__main__':
	prime_number_list = sieve_of_eratosthenes(10)
	print(prime_number_list)
	'''
	# Result
	square_root: 3
	i: 2
	j: 4
	j: 6
	j: 8
	j: 10
	i: 3
	j: 6
	j: 9
	[2, 3, 5, 7]
	'''

view raw python_algorithm_sieve_of_eratosthenes.py hosted with ❤ by GitHub