728x90
수학에서 정수론은 수의 성질을 탐구하고 공부하는 분야를 뜻합니다.
모든 정수론을 공부하는 것은 비효율적이니 코딩테스트에 자주 등장하는 소수와 호제법 부분을 다루겠습니다.
[소수 구하기]
- 자기 자신보다 작은 두 수의 곱으로 표현할 수 없는 1보다 작은 자연수
- 1과 자기 자신 이외의 약수가 존재하지 않는 수
[에라토스테네스의 체]
- 구하고자 하는 소수의 범위만큼 1차원 배열을 생성합니다.
- 2부터 시작하고 현재 숫자가 지워지지 않을때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 이때 처음으로 선택된 숫자는 지우지 않습니다.
- 범위의 끝값의 제곱근까지 과정을 반복하고 2번 과정을 반복하고 남아 있는 모든 수를 출력합니다.
ex) 1부터 30까지의 수 중 소수를 구하기
- 1은 소수가 아니므로 삭제합니다.
- 2부터 시작하고, 2의 배수를 모두 삭제합니다. 처음으로 선택된 2는 삭제하지 않습니다.
- 다음으로 지워지지 않은 수 3을 선택하고, 3의 배수를 삭제합니다. 처음으로 선택된 3은 삭제하지 않습니다.
- 과정을 반복하다가 남은 수를 출력합니다.
- 2 3 5 7 11 13 17 19 23 29
시간 복잡도 O(Nlog(logN))
2중 for문으로 구현하지만, 배수를 삭제하는 연산을 함으로써 실제 구현에서는 바깥쪽 for문을 생략하는 경우가 빈번합니다.
백준 1929 실버 2
- 3~16의 원소를 담을 배열을 생성하고, 에라토스테네스의 체 원리를 적용합니다.
더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
package numberTheory;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class _1929_소수구하기 {
//일반적인 소수 구하기 방법
/*
2이상의 자연수를 자기 자신보다 작은 수로 나눴을 때, 나머지가 0이 아닌 수를 찾습니다.
문제의 두 수의 최대 범위가 1,000,000이므로 시간 초과가 날 수 있다.
일단 비교를 위해 시간초과가 나도록 문제를 풀어보겠다.
*/
//시간초과가 나는 일반적인 방법
/*
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
OUT:
for(int i=M; i<N;i++) {
for(int k=2; k<i;k++) {
if(i%k == 0) {
continue OUT; //추가하지 않고 다음으로 넘어감
}
}
sb.append(i).append(' ');
}
System.out.println(sb);
}
*/
//시간 복잡도를 줄인 방법 2
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int arr[] = new int[N+1];
//0번지는 버리고 1은 어차피 소수가 아니니까 버림
for(int i=2;i<=N;i++) {
arr[i] = i;
}
//N의 제곱근 까지만 탐색하면 된다.
//N = a*a라고 가정할 때, a는 N의 제곱근보다 클 수 없다.
//예를 들어 16의 범위까지 소수를 구할 때, 16 = 4 * 4로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게된다.
//4보다 큰 약수는 4보다 작은 수의 배수로 지울 수 있습니다.
for(int i=2;i<=Math.sqrt(N);i++) {
if(arr[i]==0) continue;
for(int k = i+i; k<=N; k+=i ) {//k의 배수값 지우기 이런식으로 내부 반복에서 값을 지우고 외부 반복에서 지워진 값을 건너 뛰면서 시간복잡도 줄이기 가능
arr[k] = 0;
}
}
for(int i=M;i<=N;i++){
if(arr[i] != 0) {
System.out.print(i + " ");
}
}
}
}
|
cs |
728x90
'알고리즘 > 문제 풀이 비법' 카테고리의 다른 글
완전 탐색(Brute Force) (0) | 2022.06.17 |
---|---|
깊이 우선 탐색DFS(Depth-First_Search) (0) | 2022.06.16 |
구간 합 (0) | 2022.05.01 |
너비 우선 탐색_BFS(Breadth First Search) (0) | 2022.04.30 |
시간복잡도 (0) | 2022.04.24 |