문제 url:
소수 구하기
문제:
🤔 문제 알아보기
전형적인 소수구하기 문제이다. 단, 범위가 주어진 것이다.
우리는 소수를 구할 때, 브루트 포스로 구할 수 있고 logN까지 반복하는 브루트 포스로 구할 수 있으며 마지막으로 에레토스테네스의 체를 이용해 풀 수 있다.
여기서는 N이하의 구체적인 숫자가 나왔기 때문에
브루트 포스보다는 에라토스테네스의 체가 효율적일 수 있다.
ChatGPT 말로는 에라토스테네스의 체는 O(NloglogN)의 시간복잡도를 가진다고 한다.
이제 코드와 함께 풀어보도록 하자
🐱👤 실제 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
//에레토스테네스의 체 구현
boolean[] not_prime = new boolean[B+1]; // 0도 포함하기 때문에 1을 더해준다.
// 0과 1은 이미 소수가 아니기 때문에 true를 반환
not_prime[0] = true;
not_prime[1] = true;
// 2 <= p <= sqrt(n)인 범위에 있는 모든 소수 p로 n을 나누어 보아,
// 나누어 떨어지지 않으면 소수이고, 나누어 떨어지면 합성수
// 그래서 반복문의 범위와 시작 i가 이런것이다.
for(int i = 2; i <= Math.sqrt(B); i++) {
// 체에 걸러진 것은 확인할 필요가 없다.
if(not_prime[i] == true) {
continue;
}
// 만약 7을 예시로 든다면, 7은 제외하고 나머지 7의 배수를 거를 수 있다.
// 근데, 왜 7 * 7 부터 시작??
// 그 이외의 7의 배수인 14, 21, 35, 42는 이미 2, 3, 5에서 걸러졌기 때문에
// 거를 수 있는 7의 배수에서 가장 작은 값이 i의 제곱이기 때문에 시작값이 이렇다.
// B까지 반복하는 이유는 B까지 우리는 출력하기 때문에
// B가 만약, 소수가 아니라면 출력되면 안되기 때문에 그런 것
for(int j = i * i; j <= B; j = j + i) {
not_prime[j] = true;
}
}
for(int i = A; i <= B; i++) {
//false인 것들만 뽑아낸다.
if(!not_prime[i]) {
sbd.append(i).append("\n");
}
}
System.out.println(sbd);
}
}
특별한 설명은 대부분 주석으로 해놨기 때문에 주석만 읽어봐도 해당 로직이 이해될 것이다.
하지만, 필자도 이전에 에레토스테네스의 체를 이용해 풀어봤음에도 막혔기 때문에 복기 차원에서 더 설명을 해보자면,
//에레토스테네스의 체 구현
boolean[] not_prime = new boolean[B+1]; // 0도 포함하기 때문에 1을 더해준다.
// 0과 1은 이미 소수가 아니기 때문에 true를 반환
not_prime[0] = true;
not_prime[1] = true;
먼저 우리는 A이상 B이하의 구체적인 범위 즉, 끝 값을 쉽게 찾을 수 있다.(B가 끝값)
이를 통해 우리는 아주 효율적으로 에라토스테네스의 체를 구할 수 있는데,
먼저 소수인지 아닌지를 판별하기 위해 boolean 타입으로 배열 객체를 생성한다. 단, 0도 포함시켜야 하기 때문에 크기는 N+1로 구한다.
※여기서 소수일 경우 false 소수가 아닐 경우 true를 초기화 한다.
그래서 변수명이 not_prime이다.
또한, 0과 1은 이미 소수가 아니지만, 다음 로직에서 0과 1에 대해 구할 수 있는 로직은 없기 때문에 선수로 입력해 놓는다.
// 2 <= p <= sqrt(n)인 범위에 있는 모든 소수 p로 n을 나누어 보아,
// 나누어 떨어지지 않으면 소수이고, 나누어 떨어지면 합성수
// 그래서 반복문의 범위와 시작 i가 이런것이다.
for(int i = 2; i <= Math.sqrt(B); i++) {
// 체에 걸러진 것은 확인할 필요가 없다.
if(not_prime[i] == true) {
continue;
}소수는
2 <= p <= sqrt(n)인 범위에 있는 모든 소수 p로 n을 나누어 보아, 나누어 떨어지지 않으면 소수이고, 나누어 떨어지면 합성수이다.
백준 1978번: 소수 찾기 <- 추가적인 내용은 해당 링크를 통해 알 수 있다.
그래서 i는 2부터 범위는 Math.sqrt()메서드를 통해 B의 제곱근까지 반복한다.
그런 다음, 만약 해당 배열의 값이 true라면 아래의 로직을 넘기는데,
이를 통해 우리는 체에 걸러진 값들을 중복해서 구하는 것을 방지할 수 있다.
// 만약 7을 예시로 든다면, 7은 제외하고 나머지 7의 배수를 거를 수 있다.
// 근데, 왜 7 * 7 부터 시작??
// 그 이외의 7의 배수인 14, 21, 35, 42는 이미 2, 3, 5에서 걸러졌기 때문에
// 거를 수 있는 7의 배수에서 가장 작은 값이 i의 제곱이기 때문에 시작값이 이렇다.
// B까지 반복하는 이유는 B까지 우리는 출력하기 때문에
// B가 만약, 소수가 아니라면 출력되면 안되기 때문에 그런 것
for(int j = i * i; j <= B; j = j + i) {
not_prime[j] = true;
}해당 로직이 에라토스테네스의 체의 가장 핵심 로직인데,
바로 체의 역할을 한다.
에라토스테네스의 체: 위키백과 <- 옆의 링크를 타서 GIF를 보면 그림으로 쉽게 이해할 수 있다.
해당 그림처럼, 2의 배수를 거르고 3의 배수를 거르고.... 계속해서 거르게 되는데
이때 여기서 j의 시작값이 i * i이다. 그 이유를 설명하자면,
만약 7일 경우를 설명해보자, 7은 일단 소수이기 때문에 체에서 걸러지지 않는다.
(시작점 조차도 7 ^ 2이기 때문에 뛰어넘어간다.)
7의 배수는 7, 14, 21, 28, 35, 42, 49.... 인데, 여기서
14, 28, 42는 2의 배수에서 걸러지고 21 은 3의 배수에서 35 은 5의 배수에서 이미 걸려졌기 때문에
걸러지지 않은 최소의 값은 결국 7의 제곱수부터이다. 그래서 7의 제곱부터 시작하여 7의 배수를 체에 거르는 것이다.
49 , 56(이미 true라서 continue), 63(이미 true라서 continue).... 이런식으로 말이다. 그래서 증가값이 j = j + i 즉( 49 = 49 + 7)로, 7의 배수를 구할 수 있다.
🤢 회고
브루트 포스로 구하는 방법도 해봐야 하는데, 요즘따라 시간이 없어 이전 문제에서 해당 방법으로 풀었기 때문에 따로 풀지 않겠다.
또한 에레토스테네스의 체 역시 일종의 템플릿처럼 공식이 존재하다 보니, 리팩토링도 진행하지 않겠다.
간간히 에레토스테네스의 체를 생각하며 지냈지만, 막상 오랜만에 풀어보니 템플릿도 기억에 잘 안나서 그런지, 바로바로 풀 지 못했다.
백준 알고리즘을 공부하면서 이미 푼 것은 풀 수 있다고 생각했는데, 이는 자만인 것 같다 시간이 난다면 꼭 복습을 해보는 것도 나쁘지 않다.. 시간이 난다면...
