소수(Prime Number)는 1보다 큰 자연수 중에서, 1과 자기 자신만을 약수로 가지는 수를 말한다.
2, 3, 5, 7, 11.. 같은 숫자들.
기본 소수 판별법 (브루트포스)
해당 수가 소수인지를 판별하는 가장 간단한 방법은 n이 주어졌을 때 n을 2부터 n-1까지의 모든 수로 나누어 보는 것이다. 만약 2부터 n-1까지의 모든 자연수로 나누었을 때 나누어떨어지는 수가 하나라도 존재하면 n은 소수가 아니다.
public static boolean isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i < n; i++) {
if (n % i == 0) return false;
}
return true;
}
Java
복사
하지만 이 방법의 시간복잡도는 이다. 큰 수에서는 매우 느리다.
개선된 방식 ( 까지만 검사)
예를 들어 16의 약수는 다음과 같다.
•
1 X 16 = 16
•
2 X 8 = 16
•
4 X 4 = 16
•
8 X 2 = 16
•
16 X 1 = 16
여기서 알 수 있는 점은 가운데 약수를 기준으로 각 등식이 대칭적인 형태를 보인다는 것이다.
2 X 8 = 16은 8 X 2 = 16과 대칭이다. 그렇기에 특정한 자연수 n이 소수인지 확인하기 위하여 바로 가운데 약수까지만 ‘나누어떨어지는지’ 확인하면 된다. 다시 말해 제곱근까지만(가운데 약수까지만) 확인하면 된다.
public static boolean isPrime(int n) {
if (n <= 1) return false;
if (n == 2) return true;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}
Java
복사
이 방법의 시간복잡도는 이다. 훨씬 효율적이기에 대부분 소수는 이 방법으로 구한다.
에라토스테네스의 체
에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다. 에라토스테네스의 체는 n보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.
1.
1은 제외
2.
2부터 시작해서 그 배수들을 모두 없앤다. (4, 6, 8,…)
3.
남은 수 중 다음 수를 찾아서 그 배수들도 모두 없앤다. (6, 9, 12,…)
4.
반복해서 까지 진행한다.
public class Eratosthenes {
public static void main(String[] args) {
int N = 100; // 100까지의 소수를 구해보자
boolean[] isPrime = new boolean[N + 1];
Arrays.fill(isPrime, true); // 초기엔 모두 소수라고 가정
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false; // i의 배수는 소수가 아님
}
}
}
for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
System.out.print(i + " ");
}
}
}
}
Java
복사