『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.
구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.
2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다.
이때, 처음으로 선택된 숫자는 소수이기 때문에 지우지 않는다.
배열의 끝까지 2번 과정을 반복한 후 배열에서 남아 있는 모든 수를 출력한다.
💡 N의 제곱근까지만 탐색하는 이유
N이 a*b라고 가정했을 때, a와 b 모두 N의 제곱근보다 클 수 없다. 따라서 N의 제곱근까지만 확인해도 전체 범위의 소수를 판별할 수 있다.
만약 16의 범위까지 소수를 구할 때 16 = 4*4로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게 된다는 뜻이다.
따라서 4까지만 확인하고 소수 판별을 진행하면 된다.
int[] A = new int[N+1];
for (int i = 2; i <= N; i++) {
A[i] = i;
}
for (int i = 2; i <= Math.sqrt(N); i++) {
if (A[i] == 0) continue;
for (int j = i+i; j <= N; j=j+i) {
A[j] = 0;
}
}
for (int i = M; i <= N; i++) {
if (A[i] != 0) {
System.out.println(A[i]);
}
}
private static long Euler(Long N) {
long res = N;
// 2부터 N의 제곱근까지 반복
for(long i=2; i <= Math.sqrt(N); i++){
if(N%i == 0){
res = res - res/i;
while(N%i == 0) {
N /= i;
}
}
}
if(N>1) {
res = res - res/N;
}
return res;
}
public static void main(String[] args) throws Exception {
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int result = gcd(N, M);
System.out.println(result);
}
private static int gcd(int N, int M) throws IOException {
int res = N % M;
if (res == 0) return M;
return gcd(M, res);
}
private static int lcm(int N, int M) throws IOException {
return (N*M) / gcd(N, M);
}