알고리즘 정리_정수론

정수론

분류

• 소수판정
• 약수 구하기
• 소인수 분해
• 유클리드 호제법
• 에라토스테네스의 체
• 1부터 n까지 x의 배수의 개수
• n!에 곱해져 있는 소수 p의 개수 구하기

소수판정

알고리즘 문제 풀이에 필요한 소수의 정의는 좀 다르다.

소수: 약수가 2개인 수

• ex) 직사각형 가로·세로 길이가 모두 정수일 때, 가로·세로 정수쌍들 중에서 차이가 작은 것
  • 가로 세로를 곱하여 소인수분해 진행
• 소수 판정은 어려운 영역은 아니지만, 반복문에 의한 높은 시간 복잡도로 시간 초과 가능성이 있다.
• N 을 소수판정 한다고 했을 때, 2부터 N의 제곱근까지 for문을 돌려보고 없으면 소수가 더 없다.

public class PrimeNumber {

    public boolean isPrime(int candidate) {
        if (candidate == 1) {
            return false;
        }
        for (int i = 2; i * i <= candidate; i++) {
            if (candidate % i == 0) {
                return false;
            }
        }
        return true;
    }
}

약수구하기

위 소수판정과 동일하다.

• N을 입력 받았으면, N의 제곱근까지만 갔을 때 상대쌍도 구할 수 있음
  • ex) N이 100일 때, 100의 제곱근은 10이다. a,b 의 다양한 쌍에 대해 a x b = 100이라 하면
  • a == b이면 둘다 100의 제곱근인 10이다.
  • 제곱수의 경우에도 동일하게 적용된다. 약수를 출력하는 문제의 경우 조건문을 추가하여 중복하여 출력되지 않도록 수정한다.
• 약수의 개수가 홀수이다. == 제곱수이다.

소인수분해(소수의곱)

위의 두 항목과는 성격이 조금 다르지만, 제곱근을 이용하여 시간 복잡도를 줄이는 로직은 동일하다.

• 예시 상황
  • N을 소인수 분해해서 차례대로 a,b,c,d,e가 나왔을 때, 다 곱하면 N이 나온다.
  • 접근 방법: N의 제곱근보다 큰 수를 두개 곱하면 N 보다 커진다.
  • 따라서, a,b,c,d,e에는 N의 제곱근 보다 큰 수가 없거나, 1개일 것이다.
  • N의 제곱근까지 for문을 통하여 N을 나누었을 때, 마지막 값이 1이 아닐 때 까지 출력한다.
    • 나머지 값까지 모두 출력하기 위함

유클리드호제법

GCD(최대공약수), LCM(최소공배수)를 구할 때 유용하다.

• ex) gcd(6,10) = gcd(6, 10-6) // gcd(a,b) == gcd(a,b-a) = gcd(a,b-a-a)
• 더이상 지울 수 없을 때 까지 숫자 둘 중 하나가 나머지 하나의 배수가 아니면 계속 반복한다.
• LCM의 경우에는, a와 b의 곱을 GCD로 나누면 된다.
• lcm(a, b) == a*b/gcd(a,b)

에라토스테네스의 체

• 2부터 N까지의 배수를 다 처리하고 남은 수가 소수다.
• 숫자들의 제일 작은 소인수를 찾고 싶을 때도 사용한다.
  • 지우는 대신 최소 소인수로 채워놓으면 됨(그 수를 지우게 했던 수)

1부터 N까지 x의 배수의 개수

N/x개 있다.

n!에 곱해져 있는 소수 p의 개수 구하기

위의 내용을 잘 조합하면 된다.