📚 소수, 소인수분해 / 최대공약수, 최소공배수

소수, 소인수분해

참고:

• 소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽
• [백준] 11653번: 소인수분해 - JAVA [자바]

소수 판별 알고리즘

2부터 판별하는 수의 √N 까지 확인하는 방법

public class Main {
    public static boolean isPrime(int num) {
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
       System.out.println(isPrime(80));
       System.out.println(isPrime(79));
    }
}

우변에 루트를 씌워주려면 → i <= Math.sqrt(num);

소인수분해 알고리즘

for(int i = 2; i <= sqrt(N); i++) {	// 또는 i * i <= N
	while(N % i == 0) {
		println(i);
		N /= i;   // *
	}
}
 
if(N != 1) {  // 이걸 써주는 이유 ↓
	println(N);
}

• 이 때 중요한 점은, N /= i로 나누고, 남은 최종 N이 두 가지 케이스로 나뉜다는 것이다.

1. N = 16일 때 (√N = 정수일 때)
   • 반복문으로 √N까지 한다고 하면 4까지 반복
     → 1이 인수분해 되는 일은 없으므로 for문 종료 → (문제 없음)
     
2. N = 34일 때 (√N = 실수일 때)
   • 반복문으로 √N까지 한다고 하면 근사값이 대략 5.83이므로 5까지 반복
     → i = 5 가 되면 for문 종료
     → N은 17이라는 인수를 갖고 있는데 출력을 못하고 종료
     
   • 즉, for반복문이 종료되었을 시점에, N ≠ 1이라면,
     N은 소수이자 인수인 것이 자명하기 때문에 한 번 더 출력해주는 조건문이 필요하다!!
     

최대공약수, 최소공배수

참고:

• 유클리드 호제법을 Java로 구현해보자
• 최대공약수, 최소공배수 구하는 방법

유클리드 호제법 (Euclidean algorithm)이란?

호제법: 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 의미.

두 개의 수 A, B가 존재하고, A를 B로 나눈 나머지를 C라고 하겠습니다. (A > B)

이 때, A와 B의 최대공약수는 B와 C의 최대공약수와 같습니다. ex. A = 21, B = 14, C = 7 → 최대공약수 7

이러한 성질을 이용해서 계속적으로 나눗셈을 진행해서 C가 0이 되었을 때, 즉 나머지가 0이 되었을 때의 나누는 수가 최대공약수가 됩니다.

최대공약수 구현 방법

1. 두 수의 최대공약수

1. 재귀

• b가 0이라면 a가 최대공약수가 된다.
• 그렇지 않으면 b와 a % b의 최대공약수를 구하기를 재귀적으로 반복하여 최대공약수를 구할 수 있다.

public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);  //이 부분이 유클리드 호제법의 핵심
}

2. 반복문

private int gcd(int max, int min) { // max=21, min=14
    while (max % min != 0) {
        int temp = max; // max=21, min=14, temp=21
        max = min; // max=14, min=14, temp=21

        // 이 부분이 유클리드 호제법의 핵심
        min = temp % min; // min=두 수를 나눈 나머지값 // max=14, min=7, temp=21
    }
    return min;
}

2. N개 수의 최대공약수

💡 해당 부분에서는 int[] arr 파라미터로 받은 배열을 순회하면서 배열에 있는 모든 수의 “최대공약수”를 구합니다.

1. result 변수를 배열의 첫 번째 값으로 초기화합니다

2. 반복문을 통해 배열의 나머지 값들과 최대공약수를 구하여 result 변수에 저장합니다.

3. 최종적으로 result 변수에 저장된 값이 배열에 있는 모든 수의 최대공약수가 됩니다.

// 두 수의 최대공약수를 일단 구하는 메서드 정의
public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

public static int gcd(int[] arr) { //int[] arr가 N수
    int result = arr[0];
    for (int i = 1; i < arr.length; i++) {
        result = gcd(result, arr[i]);
    }
    return result;
}

최소공배수 구현 방법

1. 두 수의 최소공배수

1. 재귀

public static int lcm(int a, int b) { //a=100, b=25, gcd(a,b)=25
    return a * b / gcd(a, b); //2500/25=100
}

2. N개 수의 최소공배수

💡 해당 부분에서는 int[] arr 파라미터로 받은 배열을 순회하면서 배열에 있는 모든 수의 “최소공배수”를 구합니다.

1. result 변수를 배열의 첫 번째 값으로 초기화합니다

2. 반복문을 통해 배열의 나머지 값들과 최소공배수를 구하여 result 변수에 저장합니다.

3. 최종적으로 result 변수에 저장된 값이 배열에 있는 모든 수의 최소공배수가 됩니다.

public static int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

public static int lcm(int[] arr) {
    int result = arr[0];
    for (int i = 1; i < arr.length; i++) {
        result = lcm(result, arr[i]);
    }
    return result;
}