소수란?
들어가기전에 소수란 무엇인지 생각을 해보자
다들 쉽게 알다시피 소수는 나 자신 N과 1을 제외한 어떤수로도 약분이 되지않는 즉, 약수가 1과 자기자신인 수를 소수라고 우리는 보통 생각한다.
여기서 추가적으로 합성수는 무엇일까? 합성수란 쉽게 말해 3개 이상의 자연수의 곱으로 이루어진 수를 합성수 라고 우리는 생각한다.
우리는 여기서 P x N = M 이라는 식을 만들기는 쉽다! 하지만 역으로 M 을 소인수 분해하여 P, N 을 찾는 것이 쉬울까?
숫자가 커질수록 쉽지 않다. 이 방식을 통해 우리는 공개키 암호화 방식으로 보안로직을 다룰 수 있다. 자세한 내용은 여기서 다루지 않겠다.
소수 찾기 1
- N 보다 작은 자연수로 모두 나누어 본다.
가장 기본적인 방법이다. N보다 작은 수로 1까지 나누었을때 나누어지지 않는다면 이 수는 소수이다. 하지만 엄청난 시간 복잡도가 예상된다. 하나씩 하니 시간 복잡도는 O(N) 이다.
소수 찾기 2
- √N 이하의 자연수들로 모두 나누어 본다.
여기서 궁금증이 생길것이다 N보다 작은 수로 나누는게 √N으로 나누는 결과와 같은 결과값을 발생시키나? 어째서?
N = P x M 이라고 해보자 만약 N이 합성수라면 P, M 이 존재할 것인데. P가 증가하면 당연히 M이 감소할것이고 M이 증가하면 P가 감소할 것이다
예시를 통해 생각해보자 36은 어떻게 나타낼 수있는가?
-
1 x 36
-
2 x 18
-
3 x 12
-
4 x 9
-
6 x 6
위와같이 나타낼수 있다 왼쪽수가 커질수록 오른쪽 수가 작아진다.
생각을 해보자 그러면 M = P / N 이 아닌가?그렇다면 N이 소수가 아니라면 √N 이하의 약수를 갖게된다. 즉 √N이하의 자연수만 확인하면 N이 소수인지 아닌지를 판별할 수 있다.
그렇다면 시간 복잡도는 방법 1과 달리 O(√N) 이다.
소수 찾기 3 (중요)
- 에라토스테네스의 체
소수를 구하는 대표적인 방법 중 하나이다.
k = 2 부터 √N 이하까지만 반복하여 자연수들중 k 를 제외한 k의 배수들을 제외시킨다
예를들어 1 ~ 100 까지의 수에서 소수를 찾는다고 가정하면
k = 2 이라면 1 ~ 100 까지 사이의 2의 배수를 모두 지운다.
k = 3 이라면 1 ~ 100 까지 사이의 3의 배수를 모두 지운다.
k = 4 경우는 k = 2에서 지워졌기때문에 넘어간다.
k = 5 이라면 1 ~ 100 까지의 사이의 5의 배수를 모두 지운다.
. . . 이렇게 √100 = 10이기에 k = 10 까지 위 방식을 진행한다.
이 방식을 통해 어떻게 소수를 구할 수 있는 것일까?
만약, 1 ~ x 까지의 수가 있는 칸을 체크하는 횟수를 따지면 아래와 같이 표현할 수 있다.
(x) + (x/2) + (x/3) + (x/4) + ... + ( 1 )
위 식을 x로 묶게 된다면
x(1 + 1/2 + 1/3 + 1/4 + ... + 1/x) 로 표현 할 수 있다.
위의 x 로 묶인 안의 값들을 조화 수 라고 부르는데 쉽게말해 조화 수열에서 부분합을 의미한다고 한다.
위 식을 시그마로 무한대로 발산하게 되면 시간 복잡도는 O(NlogN) 이 나오게 된다.
하지만 우리는 알고싶은건 중복된 수를 검사하지 않는다는 것이다. 여기서부터는 백준 1939번 문제를 예시로 설명을 마쳐보겠다.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
boolean[] prime = new boolean[M + 1]; // M까지의 배열을 선언해준다 기본 값은 false
solution(prime);
StringBuilder sb = new StringBuilder();
for (int i = N; i <= M; i++) { // 0 ~ M까지 모두 구해놓은 다음 N부터 M 까지만 추출해서 값을 sb.append 해주는 것이다.
if (!prime[i]) {
sb.append(i).append("\n");
}
}
System.out.println(sb);
}
static void solution(boolean[] prime) {
prime[0] = prime[1] = true; // 0, 1 은 제외
for (int i = 2; i < Math.sqrt(prime.length); i++) { // 루트 prime의 길이까지만 체크한다.
if (prime[i]) continue;
for (int j = i * i; j < prime.length; j += i) { // 이부분이 핵심인데 i*i는 일단 예로 5가된다면 그전에 2,3 할떄 5*2, 5*3을 했기때문에 5 * 5부터 시작을 하는거다.
// j += i는 i 의 배수를 제거하기위한 값이다 25, 30, 35, 40 ...
prime[j] = true;
}
}
// 위 이중 for문을 통해 약수가 잇는것들은 모두 true가 되고 false인 것들만 추출되게 된다.
}
}
