JAVA로 소수 찾기
Goal
- 소수 찾는 방법을 코드로 구현할 수 있다
Introduction
코딩 테스트 문제를 풀면서 자주 나오는 문제로 소수를 찾는 문제가 있습니다. 이러한 문제를 푸는 방법도 구현 방식에 따라 좋은 알고리즘이 있기 때문에 한번 알아보겠습니다.
JAVA로 소수 찾기
1. n보다 작은 자연수로 나누기
가장 기본적인 방법으로 n보다 작은 자연수를 for문으로 모두 나눠보는 방법이다.
임의의 수 n이 1과 n을 제외한 다른 수를 약수로 갖고 있다면 그 수는 소수가 아니고, 만약 다른 약수가 없다는 그 수는 소수일 것이다.
public static void getPrimeToDivideAllNumber(int n) {
if (n < 2) {
System.out.println("소수가 아닙니다.");
return;
}
// 1과 0은 소수가 아니다
if (n == 2) {
System.out.println("소수입니다.");
return;
}
// 2는 소수다
for (long i = 2; i < n; i++) {
if (n % i == 0) {
System.out.println("소수가 아닙니다.");
return;
}
// n보다 작은 숫자와 나누어지면 소수가 아니다
}
System.out.println("소수입니다.");
// 위에 있는 모든걸 통과하면 소수가 된다
}
2이상 n미만의 수 중에서 나누어 떨어지는 수가 있다면 소수가 아니다.
위 알고리즘은 Big O(N)이다.
1백만의 숫자에서 소수를 구하는데 걸리는 시간은 대략 94초 걸린다.
2. n√n이하의 자연수들로 나눠 보기
위에 있는 방법을 조금 변형된 알고리즘으로 n을 √n 이하의 자연수들만 나누는 방법이다.
소수를 판별하는 것은 결국 1과 자신을 제외한 다른 자연수를 약수로 갖고 있으면 안된다든 의미이다.
public static void getPrimeToDivideByRoot(int n) {
if (n < 2) {
System.out.println("소수가 아닙니다.");
return;
}
// 1과 0은 소수가 아니다
if (n == 2) {
System.out.println("소수입니다.");
return;
}
// 2는 소수다
for (long i = 2; i <= Math.sqrt(n); i++) {
// 여기에 있는 i <= Math.sqrt(n)이 된다.
if (n % i == 0) {
System.out.println("소수가 아닙니다.");
return;
}
}
System.out.println("소수입니다.");
// 위에 있는 모든걸 통과하면 소수가 된다
}2 이상 √N 이하의 수 중에 나누어 떨어지는 수가 존재한다면 소수가 아님을 이용한 소수 판별법이다.
또한, 위 알고리즘의 시간복잡도는 당연히 √N 이하의 수까지 모든 수를 검사하므로 O(√N) 이다.
1백만의 숫자에서 소수를 구하는데 걸리는 시간은 대략 0.2초 걸린다. 첫 번째 방법에 비하면 매우 빠르다.
3. 에라토스테네스의 체를 이용
소수를 구하는 대표적인 방법으로 "i = 2부터 √n이하까지 반복하여 자연수들 중 i를 제외한 i의 배수들을 제외시킨다."
방법은 위와 같다.
i = 2 이면 2 를 제외한 2의 배수를 모두 지워주고,
i = 3 이면 3 을 제외한 3의 배수를 모두 지워주고,
(4는 이미 i = 2 에서 제외되어 넘어간다.)
i = 5 이면 5 를 제외한 5의 배수를 모두 지워주고..
이렇게 하여 k = √N 까지 반복하는 방법이다.
public class GetPrimeNumber {
public static boolean[] prime;
public static void main(String[] args) {
Instant start = Instant.now();
int n = 100_000_000;
getPrimeToEratosthenesOfChe(n);
int x = 0;
for(int i = 0; i < prime.length; i++) {
if(prime[i] == false) {
x++;
}
}
Instant end = Instant.now();
System.out.println("실행 시간 : " + Duration.between(start,end).toMillis() + "ms");
System.out.println(n + "의 숫자까지 모두 " + x + "개 소수가 있습니다.");
}
public static void getPrimeToEratosthenesOfChe(int n) {
prime = new boolean[n + 1];
if (n < 2) {
return;
}
prime[0] = prime[1] = true;
// 체크된 배열은 다음 반복문으로 skip
for (int i = 2; i <= Math.sqrt(n); i++) {
if (prime[i]) {
continue;
}
// i의 배수를 걸러주는 반복문
// 소수가 아닌 index = true
for (int j = i * i; j < prime.length; j = j + i) {
prime[j] = true;
}
}
// 소수인 index는 false로 남는다.
}
}구현부를 살펴보면 먼저 boolean[] 배열 prime 변수를 선언하고 getPrimeToEratosthenesOfChe 메소드를 실행하여 index마다 소수라면 false를 할당하고 소수가 아니면 true를 할당하여 거대한 배열 형태의 체를 만드는 것이다. 그리고 소수인지 아닌지 판별하고 싶다면 해당하는 배열 index에 값이 true인지 false인지 체크하면 끝.
위의 2가지 방법에 비해서도 매우 빠른 시간으로 1억의 숫자에서 소수를 구하는 시간은 1초정도 밖에 걸리지 않는다.
참조
