문제 url:
소수 찾기
문제:
🤔 문제 알아보기
먼저 소수에 대해서 자세히 알아보도록 하자.
소수란?
2 <= p <= sqrt(n)인 범위에 있는 모든 소수 p로 n을 나누어 보아, 나누어 떨어지지 않으면 소수이고, 나누어 떨어지면 합성수이다. 즉, 소수는 양의 약수로 1과 자신만을 가진 자연수이며 합성수는 양의 약수가 1과 자기자신을 포함하여 3개 이상인 자연수이다.
[네이버 지식백과] 소수 [prime number, 素數] (두산백과 두피디아, 두산백과)
즉, 1 과 자기 자신만을 약수로 가지며, 2 부터 판별하려는 수 직전까지 하나씩 나눠보면서 나누어 떨어지는 수가 없다면 소수고, 나누어 떨어지는 수가 있다면 소수가 아닐 것이다.
소수에 대해서 자세히 알아보았다. 그렇다면 이를 코드로 생각해본다면?
N이 소수인지를 알고 싶을 때는 2부터 시작해서 sqrt(n)번만큼 반복하면 해당 코드가 소수인지 아닌지를 판별할 수 있는 것이다.
그럼 코드로 보여주면서 설명해보록 하겠다.
🐱👤 실제 코드
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));
// N을 입력받지만, 사실 사용할 때가 없기 때문에 변수에 정의하지 않는다.
br.readLine();
StringTokenizer st = new StringTokenizer(br.readLine());
int count = 0; // 소수가 몇개인지 판별하기 위한 변수
// 공백으로 구분된 숫자 개수만큼 반복하기 위한 while문
// hasMoreTokens() -> StringTokenizer 클래스 객체에서
// 다음에 읽어 들일 token이 있으면 true, 없으면 false를 return한다.
while(st.hasMoreTokens()) {
int prime_num = Integer.parseInt(st.nextToken());
//1은 소수가 아니므로 continue;
if (prime_num == 1) {
continue;
}
// 소수인지 아닌지를 판별하기 위한 불린 변수
boolean isPrime = true;
for (int i = 2; i <= Math.sqrt(prime_num); i++) {
if(prime_num % i == 0) {
isPrime = false;
}
}
if(isPrime) {
count++;
}
}
System.out.println(count);
}
}
코드 자체는 난해하지 않아 어렵지 않을꺼라 생각해서
주석문으로도 해석이 가능할 것이라 생각해 코드 해석을 따로 진행하지 않겠다.아까 위에서 소수에 대해서 찾아봤을 때
"2 <= p <= sqrt(n)인 범위에 있는 모든 소수 p로 n을 나누어 보아, 나누어 떨어지지 않으면 소수이고, 나누어 떨어지면 합성수이다."
라는 글귀를 본 적 있다. 이를 통해서 우리는 아래의 코드처럼 짤 수 있던 것이다.
for (int i = 2; i <= Math.sqrt(prime_num); i++) {
if(prime_num % i == 0) {
isPrime = false;
}
}이렇게 코드를 짜게 되면 N번째까지 반복할 필요가 없기 떄문에 시간 복잡도 O(√N)의 값을 가지며 더 빠르게 찾을 수 있는 것이다.
✨ 해석 및 풀이
중구난방으로 적으니 무슨말인지 이해 못하고 뒤로가기를 누를 수 있다. 누르지 마요ㅠㅠ
그래서 보다 정리해서 다시 해석해보고자 한다.
1번. 2 ~ N-1까지 반복하는 코드
//1은 소수가 아니므로 continue;
if (prime_num == 1) {
continue;
}
for (int i = 2; i < prime_num); i++) {
if(prime_num % i == 0) {
isPrime = false;
}
}위 코드는 2부터 prime_num-1까지 반복했을 때를 의미하는 코드이다. 1은 소수가 아니기 때문에 예외 처리를 해줄 필요가 존재한다.
그 후 2 ~ prime_num -1까지 반복해서 나머지가 0인지 확인하는 코드이다.
해당 시간 복잡도는 O(N)으로 즉, 반복한 횟수 N만큼 시간이 든다.
2번. 2 ~ √prime_num까지 반복하는 코드
//1은 약수가 아니므로 continue;
if (prime_num == 1) {
continue;
}
for (int i = 2; i <= Math.sqrt(prime_num); i++) {
if(prime_num % i == 0) {
isPrime = false;
}
}위 코드는 2부터 √prime_num 까지 반복했을 때를 의미하는 코드이다. 1은 역시 소수가 아니므로 예외처리를 해주며
그 후 2 ~ √prime_num까지 반복해서 나머지가 0인지 확인한다.
해당 시간 복잡도는 O(√N)으로, 1번 방법보다 효율적이다.
그렇다면 왜 2번이 가능한지 다른 블로그 글을 통해 알아보도록 하자.
11 이라는 수를 판별한다고 가정하면,
11 % 2 ⇨ 약수 아님
11 % 3 ⇨ 약수 아님
11 % 4 ⇨ 약수 아님
11 % 5 ⇨ 약수 아님
11 % 6 ⇨ 약수 아님
11 % 7 ⇨ 약수 아님
11 % 8 ⇨ 약수 아님
11 % 9 ⇨ 약수 아님
11 % 10 ⇨ 약수 아님
이런식으로 구하여 11이 소수임을 알 수 있을것이다.
숫자가 A X B의 합성수(Number = A X B)라고 볼 때
(1 <= A, B < Number)와 같은 부등식을 세울 수 있다.
여기서 만약 A와 B가 Number의 제곱근보다 커진다면 모순이 생길 수 있다.
A, B > √Number
-> A X B > Number (즉 A X B = Number 가 성립되지 않는다는 걸 알 수 있다.)
그래서 결론을 낸다면
합성수 Number = A X B에서 A 또는 B중 적어도 하나는 √Number보다 작거나 같다.
다른 예를 들어 12의 약수를 계산해보면
1, 2, 3, 4, 6, 12 그리고 12의 제곱근은 3.46이다.
즉 이를 공식에 대입해보면
1, 2, 3 까지 나누어 떨어지는 수는 곧 12, 6, 4에 대응한다.
이를 또 4 이상부터 검사한 값을 들여다 보면
12 / 4 = 3 ... 0 -> 약수
12 / 5 = 2 ... 2 -> 약수 아님
12 / 6 = 2 ... 0 -> 약수
12 / 7 = 1 ... 5 -> 약수 아님
12 / 8 = 1 ... 4 -> 약수 아님
12 / 9 = 1 ... 3 -> 약수 아님
12 / 10 = 1 ... 2 -> 약수 아님
12 / 11 = 1 ... 1 -> 약수 아님
12 / 12 = 1 ... 0 -> 약수 아님
즉, 12의 제곱근 3.46 이상으로 수를 나누면 두 가지의 경우가 존재한다.
- 기존에 나누었던 1, 2, 3 등, 이전에 검사했던 수 중 약수인 수를 약수로 갖는다.
- 약수가 아니다.
그렇기에 소수를 판별 혹은 약수를 판별할 때 N-1까지 반복하는 것이 아닌 N의 제곱근까지 검사하면 되는 것이다.
👀 3번. 에라토스테네스의 체
이 친구는 소수를 구하는데, 가장 대표적인 방법 중 하나라고 한다.
이것이 무엇인지 네이버에 검색해보니,
"2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다." 라고한다.
이것을 조금 더 보면은
2부터 n까지의 숫자중에서 에라토스테네스의 체로 소수를 찾으려면,
2부터 시작해 n까지의 자연수를 차례로 쓴다. (2, 3, 4, ..., n)
그리고 2 이외의 2의 배수를 지운다(p=2). 이때 2가 최초의 소수가 된다.
그 다음 소수인 3을 제외한 3의 배수를 지운다(p=3).
이 방법을 다음에 지울 소수, 즉 p의 제곱이 n 보다 커질 때까지, 이 방법을 계속한다(p^2≥n).
이런식으로 반복하면 체로 친 것처럼 끝에 남는 수가 있다. 이 수가 소수이다.그러면 에라토스테네스의 체로 한번 문제를 풀어보도록 하자.
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int max = Integer.parseInt(br.readLine());
// 0부터 시작하기 떄문에 max+1을 하는것.
boolean[] prime_num = new boolean[max +1];
// 0과 1은 소수가 아니기 때문에 체에 거르고 시작해야 하니
//true(체에 걸러진건 true로 보자)
prime_num[0] = true;
prime_num[1] = true;
// max값의 제곱근까지 하는건, 제곱근 이상의 값은 결국 이전의 값에 대응하기 때문.
for (int i = 2; i <= Math.sqrt(max); i++) {
// 체에 걸러진건 확인할 필요가 없기 떄문이다.
if(prime_num[i] == true) {
continue;
}
for(int j = i * i; j < max; j = j + i) {
prime_num[j] = true;
}
}
// 배열 인덱스가 소수라면 false로 아니라면 true로 되어있을것이다.
for(int i = 0; i < max+1; i++) {
if(prime_num[i] == false) {
System.out.print(i + " ");
}
}
}
}
여기서 가장 중요한 것은 바로 해당 알고리즘이다. 이를 챗gpt에 분석시켜보니
for(int j = i * i; j < max; j = j + i) {
prime_num[j] = true;
}이 부분은 현재 검사 중인 소수의 배수를 찾아내는 부분입니다.
1. for(int j = i * i; j < Max + 1; j = j + i) {
- 이 부분은 현재 검사 중인 소수의 배수를 찾아내는 부분입니다.
- i x i에서 시작하는 이유는 이미 2부터 i-1까지의 배수는 이전 단계에서 걸러졌기 때문에, i의 배수 중 가장 작은 수는 i x i 입니다.
- 예를 들어, i = 3이라고 가정해 봅시다. 이 때 3의 배수 중에서
가장 작은 수는 3 x 3 = 9입니다. 따라서 여기서부터 3의 배수를 걸러내면 됩니다.
- j < Max + 1;
- j가 Max를 초과하지 않는 한도 내에서 반복됩니다.
- 배열 Prime의 크기는 Max + 1로 설정되었기 때문에, j가 Max + 1을 초과하지 않도록 하여 배열의 인덱스를 초과하는 오류를 방지합니다.
- j = j + i
- i의 배수를 찾아내기 위해 j에 i를 더해가며 반복합니다.
- 예를 들어, i = 3일 때 j는 9부터 시작하고, 그 다음에는 12, 15, 18 등으로 i씩 증가하는 수열을 형성하여 i의 배수를 찾아냅니다.
- ex) i = 2이라면 현재 j는 2 x 2로 = 4 그 다음 숫자는 4 + 2로 6부터 시작하게 되는 것이다.
여기서 Max +1이 나는 조금 이해가 안되서 코드를 처보았다. (머리가 나쁘다)
근데 우리가 위에서 0까지 포함시켰다는 것을 생각하고 보니,
마지막 Max값이 들어갈 자리에는 이미 Max-1값이 들어가 있기에 정작 Max값이 입력되지 않은 것을 확인할 수 있었고, 그래서 아하! Max+1을 해줘야 하는것을 알았다.
🤢 회고
나이를 먹었는지... 예전에 잘 풀던 소수 문제를 못 풀어 좀 많이 화가 났었다.
이번에 공부를 했으니 이제는 절대 까먹지 않고 풀 수 있도록 하자
❤ 참고 자료
