January 2, 2023

에라토스테네스의 체

대표적인 소수 판별 알고리즘이다.

알고리즘

일반적인 소수 판별기

int isPrimeNumber(int num) {
	int end = sqrt(num);

	for (int i = 2; i <= end; ++i) {
		if (num % i == 0) return 0;
	}
	
	return true;
}

2부터 판별을 원하는 숫자의 제곱근까지 원하는 숫자를 나누어 나머지가 0이 되게 하는 값이 있는지 확인한다. 나머지를 0으로 만드는 값이 존재한다면 해당 숫자는 소수가 아니고, 그렇지 않다면 소수이다.

<aside> 💡 시간 복잡도 측면에서 좋지 않다. O(sqrt(n))

</aside>

에라토스테네스의 체

n = 1000
a = [False, False] + [True] * (n - 1)
primes = []

for i in range(2, int(sqrt(n)) + 1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False

print(primes)

1. 배열을 생성하여 값을 초기화한다.
2. 2부터 시작하여 구하려는 범위의 제곱근까지 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다. (자기 자신은 지우지 않는다.)
3. 이미 지워진 숫자는 건너뛴다.
4. 2부터 남아있는 숫자들을 출력한다.

<aside> 💡 시간 복잡도는 $O(nlog(logn))$이다.

</aside>

<aside> 💡 제곱근 까지만 계산하는 이유 예를 들어, 36의 약수는 1 2 3 4 6 9 12 18 36이다. 36의 제곱근 6을 기점으로 대칭이 형성된다. 3과 12를 예로 든다면 36 = 3 * 12 = 12 * 3 이다. 즉, 36을 3으로 나누는 것과 12로 나누는 것은 완전히 같은 행위이다.

</aside>

참고 링크