문제 풀이 전 이론 - 1
- 해당 문제는 소수 찾기1과 동일하지만, 입력에서 최악의 경우가 실행 시간에 치명적인 영향을 미친다.
- 기존의 방법으로 풀었으면 약수를 알아내는 시간 O($\sqrt{N}$)과 모든 N에 대한 O(N)로 인해 O(N$\sqrt{N}$)이 될 것이다.
- 일단 최악의 경우가 백만이라고 하면 의심해봐야 한다...(꿀팁)
- 이에 대한 문제를 효율적으로 해결할 수 있는 방법은 에라토스테네스의 체 알고리즘을 사용하는 것이다.
문제 풀이 전 이론 - 에라토스테네스의 체
- 1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다.
- 이를 이용하면 N이 100만인 경우 + 테스트케이스 문제일 때, 모든 소수를 크기가 100만인 배열에 미리 저장해놓고, 입출력할 수 있다.
- 에라토스테네스의 체 알고리즘은 아래와 같은 순서로 이루어져 있다.
- 1. 2부터 N까지 모든 수를 써놓는다.
- 2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
- 3. 그 수는 소수이다.
- 4. 이제 그 수의 배수를 모두 지운다.
- 2부터 100까지 모든 수를 써놓았다.
- 아직 지워지지 않은 수 중에서 가장 작은 수는 2이다.
- 2의 배수(빨간 글씨)를 찾아 모두 지운다.
- 아직 지워지지 않은 수 중에서 가장 작은 수는 3이다.
- 3의 배수(빨간 글씨)를 모두 지운다.
- 아직 지워지지 않은 수 중에서 가장 작은 수는 5이다.
- 5의 배수(빨간 글씨)를 모두 지운다.
- 보아하니, 다른 수 들은 2와 3의 배수로 인해 이미 모두 지워진 상태이고 (5 x 5~)만 지우면 된다.
- 아직 지워지지 않은 수 중에서 가장 작은 수는 7이다.
- 7의 배수(빨간 글씨)를 모두 지운다.
- 보아하니, 다른 수 들은 2와 3의 배수로 인해 이미 모두 지워진 상태이고 (7 x 7~)만 지우면 된다.
- 이제 다음은 11인데, 이미 2,3,5,7의 배수로 인해 이미 모두 지워졌으므로 (11 x 11~)만 지우면 되는데, 그러면 100을 넘어가므로 고려할 필요가 없다. 따라서 여기까지만 구하면 된다.
문제 풀이
- 에라토스테네스의 체 알고리즘을 구현한다.
- m과 n사이의 소수를 구하면 되므로, n+1만큼 크기의 배열을 선언한다.
- 지운 수는 true, 지워지지 않은 수(소수)는 false이다.
소스코드
public class Main {
public static void main(String[] args) {
//에라토스테네스의 체
Scanner scan = new Scanner(System.in);
int m,n;
while(true) {
m = scan.nextInt();
n = scan.nextInt();
if(m <= n) {
break;
}
}
boolean[] check = new boolean[n+1];
EratosTenes(check, n);
for(int i = m; i <= n; i++) {
if(check[i] == false) {
System.out.println(i);
}
}
}
public static void EratosTenes(boolean[] check, int n) {
check[0] = check[1] = true;
for(int i = 2; i*i <= n; i++) { //N이 100인 예시에서도 보았듯이 11부터는 굳이 배수를 구할 필요가 없다. 11*11은 100을 넘기기 때문 그리고 이미 지워야할 수들은 모두 지워짐.
if(check[i] == true) {
continue;
}
for(int j = i+i; j<=n; j+=i) { // 2 , 3 본인들은 냅두고 J+=i로 배수만큼 반복 4,6 등은 이미 지워짐 i+i하면 소수인 본인들은 안지워짐.
check[j] = true;
}
}
}
}
출력
느낀점
아직 몇 문제 풀어보진 않았지만 점점 문제를 노련하게 보는 눈이 생기고, 문제를 보자마자 효율성을 따져야 하는지 아니면 직관적으로 해석해서 풀어도 되는지 보이기 시작한다.
'기타등등 > 알고리즘 기록' 카테고리의 다른 글
[Unity C#] 거품 정렬 (0) | 2021.03.21 |
---|---|
[JAVA] 백준 6588 - 골드바흐의 추측 (0) | 2021.02.24 |
[JAVA] 백준 1978 - 소수 찾기 (0) | 2021.02.24 |
[JAVA] 백준 2609 - 최대공약수와 최소공배수(유클리드 호제법) (0) | 2021.02.24 |
[JAVA]백준 17425 - 약수의 합 (0) | 2021.02.20 |