[알고리즘] 소수 구하기

소수

---

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다.

예를 들어, 5는 1 ×5 또는 5 ×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수입니다.

그러나 6은 자신보다 작은 두 숫자의 곱(2 ×3)이므로 소수가 아닌데,

이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수나 비소수라고 합니다.

 

에라토스테네스의 체

---

소수를 구하는 대표적인 방법으로 에라토스테네스의 체가 있습니다.

에라토스테네스의 체 알고리즘은 다음과 같습니다.

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성합니다.
2. '2'부터 시작해 특정 수의 배수에 해당하는 수를 모두 지웁니다. 이때 특정 수 자신은 지우지 않습니다.
3. 배열의 끝까지 2를 반복합니다.

By 독일어 위키백과의 SKopp

 

에라토스테네스의 체 구현

---

boolean[] arr = new boolean[n + 1]; // n은 찾을 범위
for (int i = 2; i < n + 1; i++) {   // true로 초기화
	arr[i] = true;
}

for (int i = 2; i <= Math.sqrt(n); i++) {
    if (!arr[i]) {
        continue;
    }

    for (int j = i + i; j <= n; j += i) {
        arr[j] = false;
    }
}

 

n의 제곱근까지만 탐색하는 이유

---

 

• 어떤 수 n이 소수인지 판별하려면 n의 약수가 있는지 확인해야 합니다.
• 만약 n이 소수가 아니라면, n은 두 수 a와 b의 곱으로 나타낼 수 있습니다 (n = a × b).
• 여기서 a와 b 둘 다 ​n의 제곱근 보다 크다면, a × b는 n보다 큽니다.

따라서 n의 약수 중 적어도 하나는 반드시 n의 제곱근 보다 작습니다.

또한 에라토스테네스의 체는 소인수를 찾는 과정이기 때문에 n보다 더 큰 약수는 지워집니다.

 

에라토스테네스의 체 시간복잡도

---

일반적으로 에라토스테네스의 체를 구현하려면 이중 for문을 사용하지만

배수를 삭제하는 for문을 생략하는 경우가 있기 때문에 실제 시간복잡도는 O(Nlog(logN))입니다.