소수 구하기
소수(prime number)는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다.
같은 의미로 1과 자기 자신 이외에 약수가 존재하지 않는 수를 말한다.
에라토스테네스의 체
- 구하고자 하는 소수의 범위만큼 1차원 배열을 생성
- 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다.
- 이때, 처음으로 선택된 숫자는 지우지 않는다.
- 배열의 끝까지 2를 반복하고 남아있는 수를 출력한다.
에라토스테네스의 시간 복잡도
이중 for문을 사용하므로 O(N^2) 으로 판단할 수 있지만 실제 시간 복잡도는 일반적으로 O(Nlog(logN)).
이유는 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하기 때문.
int k = 20; // 1부터 20 사이의 소수를 구한다.
int[] arr = new int[k + 1]; // 배열의 크기는 0부터 k까지. 즉, k + 1
for (int i = 2; i < k + 1; i++) {
arr[i] = i;
}
// 전체 배열을 확인하지 않고 제곱근(Math.sqrt())까지만 연산!
for (int i = 2; i < Math.sqrt(k + 1); i++) {
if (arr[i] == 0) continue;
// arr[i]의 배수를 0으로 지운다
// 아래는 배수에만 접근하는 for문 조건!
for (int j = i + i; j < k + 1; j = j + i) {
arr[j] = 0;
}
}
for (int i = 2; i < k + 1; i++) {
if (arr[i] != 0 && arr[i] >= n) System.out.println(arr[i]);
}
오일러 피
오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.
*pass
유클리드 호제법
유클리드 호제법(euclidean algorithm)은 두 수의 최대 공약수를 구하는 알고리즘.
일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시.
- 큰 수를 작은 수로 나누는 MOD(%) 연산을 수행
- 앞 단계에서의 작은 수와 MOD 연산 결과값(나머지)으로 다시 MOD 연산을 수행
- 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택
private static int ea(int big, int small) {
int namerge = 0;
while (true) {
namerge = big % small;
if (namerge == 0) return small;
else {
big = small;
small = namerge;
}
}
}
private static int ea_recursive(int big, int small) {
if(small == 0) return big;
return ea_recursive(small, big % small);
}
확장 유클리드 호제법
*pass