안녕하세요 이번 시간에는 소수 구하기 알고리즘에 대해 알아보는 시간을 갖도록 하겠습니다.
소수를 빠르게 구하는 알고리즘은 에라토스테네스의 체입니다. 에라토스테네스의 체는 다음의 방식으로 동작합니다.
- 구하고자 하는 소수의 범위만큼 1차원 배열을 생성
- 2부터 시작하며 현재 숫자가 지워지지 않을 때 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지우기
2-1. 이 때 처름으로 선택된 숫자는 지우지 않음
2-2. 1은 소수가 아니기 때문에 지움 - 배열의 끝까지 2번 과정을 반복한 후 배열에서 남아 있는 모든 수 출력
에라토스테네스의 체의 예시를 백준 1929(소수 구하기) 문제를 통해 구현해보겠습니다. M 이상 N 이하 소수를 모두 출력하는 문제로 2부터 N의 제곱근까지 탐색하여 소수가 아닌 경우 continue하며 반복문 내부에 ix2부터 N까지 j += i 만큼 이동하여 소수가 아닌 수를 체크합니다.(ix2, ix3, ... ,) 여기서 1은 소수가 아니기 때문에 최초 초기화 시 체크해야 합니다.
import java.util.*;
import java.io.*;
class Main{
static boolean[] check;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
check = new boolean[N+1];
check[1] = true;
for(int i=2;i<=Math.sqrt(N);i++){
if(check[i]) continue;
for(int j=i+i;j<=N;j+=i){
check[j] = true;
}
}
StringBuilder sb = new StringBuilder();
for(int i=M;i<=N;i++){
if(!check[i]) sb.append(i).append("\n");
}
System.out.println(sb);
}
}백준 1456(거의 소수) 문제의 경우 소수의 N제곱꼴인 수가 A 이상 B 이하 범위에 몇 개인지를 출력하는 문제입니다. N의 제곱근까지의 소수의 개수를 구한 후 자기 자신의 소수를 계속 곱해가면서 범위 내에 존재하면 카운트합니다.
백준 1747(소수 & 팰린드롬) 문제의 경우 N보다 크거나 같고 소수이면서 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수 중 가장 작은 수를 구하는 문제입니다. 최대 범위까지의 소수를 구하고 투 포인터를 이용해서 뒤의 수와 앞의 수가 모두 같으면 카운트합니다.
백준 1016(제곱 ㄴㄴ수) 문제의 경우 1보다 큰 제곱수로 나누어 떨어지지 않는 수의 개수가 구간 내에 몇 개 있는지 출력하는 문제입니다. 이 문제는 에라토스테네스의 체를 응용하여 구간 내의 제곱수의 개수를 구하면 됩니다. 2의 제곱수부터 구간 내의 최대 제곱수까지 탐색하여 시작값이 반드시 1이 아니기 때문에 제곱수보다 최솟값이 더 크다면 해당 제곱수 계산 연산을 생략하기 위해 시작 인덱스 = 최솟값%제곱수==0 ? 최솟값/제곱수 : 최솟값/제곱수+1로 설정합니다. 이렇게 구한 시작 인덱스부터 제곱수x인덱스 값이 최댓값 이내에 존재할 때까지 제곱수x인덱스와 최솟값의 차이를 체크합니다.
