소수 구하기 (에라토스테네스의 체)
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 start = Integer.parseInt(st.nextToken()); // 시작 수
int end = Integer.parseInt(st.nextToken()); // 종료 수
int[] array = new int[end+1];
for (int i = 2; i <= end; i++) {
array[i] = i; // 각각의 인덱스 값으로 배열 초기화하기
}
for (int i = 2; i <= Math.sqrt(end); i++) { // end의 제곱근까지만 수행하기
if (array[i] == 0) {
continue; // 소수가 아니면 넘어감
}
for (int j = i + i; j <= end ; j = j + i) { // 배수 지우기 (i의 배수만큼 이동해야하기 때문에 j = j + i)
array[j] = 0; // 이 수가 소수가 아니라는 것을 표시
}
}
for (int i = start; i <= end; i++) {
if (array[i] != 0) {
System.out.println(array[i]); // 배열에서 소수인 값 출력하기
}
}
}
}
- 에라토스테네스의 체에서 가장 중요한 포인트는 end 의 제곱근까지만 수행하고, 배수를 지우는 것이다.
- N의 제곱근까지만 탐색하는 이유 :
N이 a * b라고 가정했을 때, a와 b 모두 N의 제곱근보다 클 수 없기 때문이다.
오일러 피 (이해도 낮음 복습할 때 다시 해보기)
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(br.readLine()); // 소인수 표현 입력
long result = n; // 결괏값
for (long p = 2; p <= Math.sqrt(n); p++) { // n의 제곱근까지만 진행하기
if (n % p == 0) { // 만약 현재 값이 소인수라면
result = result - result / p; // 결괏값 = 결괏값 - 결괏값/현재값
while (n % p == 0) { // n에서 현재 소인수 내역을 제거하기
n /= p;
}
}
}
if (n > 1) { // n이 마지막 남은 소인수 구성일 때
// 반복문에서 제곱근까지만 탐색했으므로 1개의 소인수가 누락되는 케이스
result = result - result / n;
}
System.out.println(result);
}
}
- 오일러 피 문제는 아직 완벽하게 이해하진 못했다. 여러 번 다시 봐야할 것 같다.
- 입력에서 자연수가 10의 12제곱까지 주어지기 때문에 int 대신 long을 사용했다.
- while (n % p == 0) 에서 2의 7제곱 * 11 이라면 2의 7제곱을 없애고 11만 남긴다. -> 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));
int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수가 주어짐
for (int i = 0; i < T; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int result = A * B / gcd(A, B);
System.out.println(result);
}
}
public static int gcd(int a, int b) {
if (b == 0) {
return a; // 만약 b가 0이면, a는 최대공약수
} else {
return gcd(b, a % b); // 작은 수, 큰 수 % 작은 수 를 재귀 함수 형태로 구현하기
}
}
}
- 두 수의 최대공배수를 구하려면, 두 수의 곱을 최대 공약수로 나눈 값을 구해야함.
- 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택! 그 후에 최대 공배수를 구해주기.
'코테 준비 > 알고리즘' 카테고리의 다른 글
[알고리즘] 그래프 (1) | 2024.03.26 |
---|---|
[알고리즘] 그리디 (0) | 2024.03.15 |
[알고리즘] 탐색 (1) | 2024.03.14 |
[자료구조] 정렬 (3) | 2024.03.12 |
[자료구조] 스택과 큐 (0) | 2024.03.06 |