EcoDev's Blog

에라토스테네스의 체(feat.Python)

1. 쉽게 떠올릴 수 있는 방법

Python

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

가장 간단한 코드이다.

1과 자기자신을 제외하고 2 ~ x - 1까지 숫자들 중에 하나라도 나누어지는 값이 존재하면 x는 소수가 아니게 된다.

시간복잡도 : O(N)

2. 시간 단축1

Python

import math

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

코드 1번에서 조금 더 시간을 단축시켰다.

어떻게 x의 제곱근까지 봐서 파악할 수 있냐? 의문이 생길 수 있는데 이 이유는

자연수의 약수는 대칭성을 보인다.

예를들어 16이라는 수가 있다고 가정해보자.

16의 약수로는 1, 2, 4, 8, 16 이렇게 존재한다.

1 * 16 = 16

2 * 8 = 16

4 * 4 = 16

8 * 2 = 16

16 * 1 = 16

이런 대칭성을 보이게 된다.

따라서 중간인 제곱근값까지만 약수를 확인해도 대칭성때문에 그 이후는 판단할 필요가 없는 것이다.

시간복잡도 : O(N**0.5)

3. 에라토스테네스의 체

위 코드들은 x라는 수가 소수인지 아닌지만 판단하는 방법이다.

그렇다면 x보다 작거나 같은 모든 소수를 찾으려면 어떤 방법을 사용해야 효과적일까?

답은 에라토스테네스의 체이다. 우선 아래 설명부터 살펴보자.

다음과 같은 순서로 알고리즘이 동작한다.

1) 2부터 x까지의 모든 자연수를 나열한다.

2) 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i 를 찾는다.

3) 남은 수 들 중 i를 제외하고 i의 배수들을 모두 제거한다.

4) 더 이상 반복할 수 없을 때 까지 2, 3을 반복한다.

1. while문 이용

Python

import math

x = 1000
ls = [True for i in range(x + 1)]

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

2. for문 이용

Python

import math

ls = [True] * n + 1

for i in range(2, int(math.sqrt(n)) + 1) :
	if ls[i] :
		for j in range(i + i, n + 1, i) :
			ls[j] = False

결과론적으로 실행시간을 상당히 줄여줄 수 있게 되어 효율적으로 소수를 찾아낼 수 있다.

시간복잡도 : O(N * log logN)

2024.10.28 추가 범위내에 있는 소수 판별할 때는 효율적이지만 단순 소수판별시에는 시간이 오히려 더 소모될 수 있다. 또한 범위가 확정되지 않은 상황에서는 오히려 불리할 수 있다.

출처 : https://www.youtube.com/watch?v=9rLFFKmKzno

에라토스테네스의 체(feat.Python)

1. 쉽게 떠올릴 수 있는 방법

Python

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

가장 간단한 코드이다.

1과 자기자신을 제외하고 2 ~ x - 1까지 숫자들 중에 하나라도 나누어지는 값이 존재하면 x는 소수가 아니게 된다.

시간복잡도 : O(N)

2. 시간 단축1

Python

import math

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

코드 1번에서 조금 더 시간을 단축시켰다.

어떻게 x의 제곱근까지 봐서 파악할 수 있냐? 의문이 생길 수 있는데 이 이유는

자연수의 약수는 대칭성을 보인다.

예를들어 16이라는 수가 있다고 가정해보자.

16의 약수로는 1, 2, 4, 8, 16 이렇게 존재한다.

1 * 16 = 16

2 * 8 = 16

4 * 4 = 16

8 * 2 = 16

16 * 1 = 16

이런 대칭성을 보이게 된다.

따라서 중간인 제곱근값까지만 약수를 확인해도 대칭성때문에 그 이후는 판단할 필요가 없는 것이다.

시간복잡도 : O(N**0.5)

3. 에라토스테네스의 체

위 코드들은 x라는 수가 소수인지 아닌지만 판단하는 방법이다.

그렇다면 x보다 작거나 같은 모든 소수를 찾으려면 어떤 방법을 사용해야 효과적일까?

답은 에라토스테네스의 체이다. 우선 아래 설명부터 살펴보자.

다음과 같은 순서로 알고리즘이 동작한다.

1) 2부터 x까지의 모든 자연수를 나열한다.

2) 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i 를 찾는다.

3) 남은 수 들 중 i를 제외하고 i의 배수들을 모두 제거한다.

4) 더 이상 반복할 수 없을 때 까지 2, 3을 반복한다.

1. while문 이용

Python

import math

x = 1000
ls = [True for i in range(x + 1)]

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

2. for문 이용

Python

import math

ls = [True] * n + 1

for i in range(2, int(math.sqrt(n)) + 1) :
	if ls[i] :
		for j in range(i + i, n + 1, i) :
			ls[j] = False

결과론적으로 실행시간을 상당히 줄여줄 수 있게 되어 효율적으로 소수를 찾아낼 수 있다.

시간복잡도 : O(N * log logN)

2024.10.28 추가 범위내에 있는 소수 판별할 때는 효율적이지만 단순 소수판별시에는 시간이 오히려 더 소모될 수 있다. 또한 범위가 확정되지 않은 상황에서는 오히려 불리할 수 있다.

출처 : https://www.youtube.com/watch?v=9rLFFKmKzno