소수를 판별해보자..!
1. 기본 코드
소수는 1과 자신으로만 나눌 수 있는 수이다.
그렇기에 기본적으로 소수 판별을 하는 코드를 작성해보자면
1을 건너뛴 2부터 자기 자신이 오기 전까지의 수를 모두 나누어 보고 나뉘어 떨어진다면, 소수가 아니고 다 통과하게 된다면 소수이다.
public class Main {
public static void main(String[] args) {
System.out.println(isPrime(14));
}
static boolean isPrime(int number){
for(int i=2;i<number;i++){
if(number % i == 0) return false;
}
return true;
}
}
이 방식은 O(n) 시간 복잡도를 가지고 있다.
2. 조금 더 생각
조금 더 생각해보자면, N번을 모두 돌리지 않아도 된다. 왜냐하면 어떤 수가 n x m 이라면 m x n 이랑 같기 때문에 제곱근 밑까지만 돌리면 모든 경우의 수를 파악할 수 있다.
16을 생각해보자면 1 x 16, 2 x 8, 4 x 4, 8 x 2, 16 x 1 이렇게 제곱근(4)까지만 파악해주면 뒤는 동일하다.
public class Main {
public static void main(String[] args) {
System.out.println(isPrime(131));
}
static boolean isPrime(int number){
int sqrt = (int) Math.sqrt(number);
for(int i=2;i<sqrt;i++){
if(number % i == 0) return false;
}
return true;
}
}이렇게 시간을 O(sqrt(n)) 만큼 줄였다.
3. 에라토스테네스
에라토스테네스의 체는 특정 숫자를 구할 때 빠른 것이 아니라 특정 구간에서 소수만을 남겨놓을 수 있다. 이렇게 전처리를 통해 이 숫자가 소수인지 빠른 판별이 가능하다.
makePrimeMap 함수를 통해 for문을 돌리는데 만약 0(소수 아님) 이 아니라면 자신의 배수를 모두 0으로 만든다.
그렇게 0이 아닌 수만 남는데 그것이 소수의 모음!
public class Main {
static int[] primeMap;
public static void main(String[] args) {
int range = 1000;
init(range);
makePrimeMap(range);
for(int i = 2; i <= range; i++) {
if(isPrime(i)) {
System.out.print(i + " ");
}
}
}
private static void init(int range) {
primeMap = new int[range+1];
for(int i=1;i<range+1;i++){
primeMap[i] = i;
}
}
private static void makePrimeMap(int range){
for(int i=2;i<=range;i++){
if(primeMap[i]==0)continue;
for(int j=i+i;j<=range;j+=i){
primeMap[j] = 0;
}
}
}
private static boolean isPrime(int number){
if(primeMap[number]==0)return false;
return true;
}
}
전처리 시간이 O(nloglogn) 만큼 걸린다! O(n)과 별로 차이 안나는 데 그 후에 범위 내의 소수를 판별할 때 O(1) 시간으로 소수를 판별 가능하다!
정리
소수를 판별하는 더 많은 방법들 (밀러-라빈, 세그먼트) 가 있지만 이정도면 보통 코딩테스트에서 활용 가능 할 것이다.
만약에 소수 판별하는 과정이 조금 필요하다면 제곱근까지만 돌려서 판별해도 좋다.
또한, 소수 판별을 지속적으로 해야할 일이 있다면 에라토스테네스의 체를 통해 전처리 후 소수를 O(1) 시간으로 추출하는 것도 좋다!
