[알고리즘] 정수론

 

 

개인 공부 후 자료를 남겨놓기 위한 목적이므로,
생략되거나 오류가 있을 수 있음을 알립니다.

 

 

---

 

목차

 

---

 

1. 소수 판정

1. 기본형

소수 판정의 기본 1부터 n까지 n이 나누어지는지 확인하면서 약수의 개수를 세어준다.

하지만 보통 문제에서는 n을 매우 크게 주기 때문에 활용하기 힘들다. (시간 복잡도 - O(n))

#include <iostream>

using namespace std;

bool check(int n)
{
    int cnt = 0;

    // 1부터 n까지 약수 검사
    for(int i = 1; i < n + 1; i++)
    {
        if (n % i == 0) cnt++;
    }

    // 약수가 2개면 소수
    if(cnt == 2) return true;
    else return false;
}

int main()
{
    int n;
    cin >> n;

    if(check(n)) // n 이 소수면
    {
        cout << L"소수다";
    }
    else
    {
        cout << L"소수가 아니다.";
    }
    return 0;
}

 

2. 최적화

12를 예를 들어 보자.

12의 약수는 다음과 같다. 1, 2, 3, 4, 6, 12

이를 두 줄로 적어 보면 다음과 같이 나오는 데 약수들이 쌍을 이루는 것을 확인할 수 있다.

 

1 12

2 6

3 4

 

1부터 $\sqrt{n}$ 까지 보니 약수가 3개. ( $\sqrt{12}$ 는 약 3.46이다. )

n의 약수는 6개가 된다. (쌍을 이룸)

 

이를 이용하면

2부터 루트 n 까지 보니 약수가 1개도 없는 경우, (루트 n)  + 1부터 n - 1까지도 약수가 없다는 것을 알 수 있다.

 

bool check(int n)
{
    // 1은 특수 케이스이기 때문에 예외처리한다.
    if(n == 1) return true;

    int cnt = 0;

    // 2부터 i * i가 n보다 작은 경우만 검사
    for(int i = 2; i * i < n + 1; i++)
    {
        if (n % i == 0) cnt++;
    }

    // 약수가 0개면 소수
    if(cnt == 0) return true;
    else return false;
}

 

3. 요약

💡
1. 2 ~ (루트 n) 까지 나눠지는지 계산해본다. (0개면 소수)
2. 1은 예외처리한다.

 

 

---

 

2. 약수 구하기

1. 기본형

int main()
{
    int n;
    for(int i = 1; i < n + 1; i++)
    {
        if(n % i == 0) cout << i << '\n';
    }

    return 0;
}

 

보통 n이 매우 크게 나오기 때문에 시간초과가 발생한다.

 

2. 최적화

소수 판정과 마찬가지로 (루트 n) 까지만 판단하면 된다.

약수는 쌍을 이루기 때문에,

12의 경우 1, 2, 3 만 구한다면 4, 6, 12를 구할 수 있게 된다.

 

❗ 단 제곱수의 경우 약수의 개수가 홀수개이기 때문에 예외처리를 해줘야 한다. 16의 약수 → 1, 2, 4, 8, 16

int main()
{
    int n;
    cin >> n;

    for(int i = 1; i * i < n + 1; i++)
    {
        if (n % i == 0)
        {
            cout << i << " ";

            // 제곱수이면서 마지막 쌍이라면, 출력하지 않음.
            if (i * i != n) cout << n / i << " ";
        }
    }

    return 0;
}

 

💡 1. 약수의 개수가 홀수 → 제곱 수 2. 약수의 개수가 짝수 → 제곱 수가 아닌 수

 

---

 

 

3. 소인수 분해

소인수 분해 : 수(합성수)를 소수의 곱으로 바꾸는 일.

72 = 2 * 2 * 2 * 3 * 3

1. 기본형

int main()
{
    int n;
    cin>> n;

    for(int i = 2; i < n + 1; i++)
    {
        if (n == 1) break;

        while(n % i == 0)
        {
            cout << i << ' ';
            n /= i;
        }
    }

    return 0;
}

 

단점 : 엄청 큰 소수인 경우인 경우에는 매우 오래 걸리게 된다.

💡 알아둘 것.
1. n의 소인수를 모두 곱하면 n이 나온다.
2. (루트 n) * (루트 n) = n이고, (루트 n) 보다 큰 값 * (루트 n) 보다 큰 값 > n 이다.
    따라서 (루트 n) 보다 큰 값은 2개이상 나올 수 없다. => (루트 n)보다 큰 소인수가 없거나 하나 있다.

 

2. 최적화

1.  (루트 n) 보다 큰 소인수가 없는 경우

int main()
{
    int n;
    cin >> n;

    // 연산에 따라 n이 계속해서 바뀌게 되므로,
    // n을 복사한 x를 만들어 계산한다.
    int x = n;

    for(int i = 2; i * i < n + 1; i++)
    {
        while(x % i == 0)
        {
            cout << i << ' ';
            x /= i;
        }
    }
    return 0;
}

 

2. (루트 n) 보다 큰 소인수가 정확히 하나 있는 경우

해당 경우에는 1번의 모든 연산이 끝난 이후에 n에 하나가 남아있다. (n이 1이 아님)

 

int main()
{
    int n;
    cin >> n;

    // 연산에 따라 n이 계속해서 바뀌게 되므로,
    // n을 복사한 x를 만들어 계산한다.
    int x = n    

    for(int i = 2; i * i < n + 1; i++)
    {
        while(x % i == 0)
        {
            cout << i << ' ';
            x /= i;
        }
    }

    if(x != 1) cout << n;

    return 0;
}

 

 

 

 

---

 

4. 유클리드 호제법

1. 8과 12의 공약수는 12 - 8의 약수이기도 하다.

2. a와 b의 공약수는 (a < b) b - a 의 약수이기도 하다.

    + a, b, a - b 는 공약수를 공유한다.

 

GCD - greatest common divisor = 최대 공약수

 

GCD(510, 20) == GCD(490, 20) == GCD(470, 20) == GCD(450, 20) …… GCD(20, 10)

 

위의 모든 GCD는 공약수를 공유한다.

 

따라서 GCD(a, b) (a > b) ⇒ GCD(b, a % b)

 

int get_gcd(int a, int b)
{
    while(a % b != 0)
    {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return b;
}

 

- 최대공약수 : 유클리드 호제법
- 최소공배수 : a * b / GCD(a, b)

 

---

 

 

5. 에라토스테네스의 체

 

 

1부터 n까지 소수 모두 구하기

1. 1 외에는 모두 소수라고 가정
2. i가 2부터 반복
3. 만약 i가 소수라면 i의 배수 모두 지우기
4. 만약 i가 소수가 아니라면 넘어간다.

 

1. 기본형

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<bool> isPrime;

int main()
{
    cin >> n;

    // 모두 true인 배열 생성
    isPrime.resize(n + 1, true);

    // 1은 예외처리
    isPrime[1] = false;

    for(int i = 2; i < n + 1; i++)
    {
        if(!isPrime[i]) continue;

        for(int j = 2 * i; j < n + 1; j += i)
        {
            ifPrime[j] = false;
        }
    }

        return 0;
}

 

2. 최적화

 

예를 들어 7의 배수를 지운다고 하자.

 

14 ⇒ 2 * 7

21 ⇒ 3 * 7

28 ⇒ 4 * 7

35 ⇒ 5 * 7

42 ⇒ 6 * 7

49 ⇒ 7 * 7

56 ⇒ 8 * 7

….

 

위와 같이 되는데, 이미 2~ 6까지의 배수는 앞선 연산들로 인해 false 처리되어있다.

따라서 i * i 부터 연산을 해주면 된다.

 

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<bool> isPrime;

int main()
{
    cin >> n;

    // 모두 true인 배열 생성
    isPrime.resize(n + 1, true);

    // 1은 예외처리
    isPrime[1] = false;

    for(int i = 2; i < n + 1; i++)
    {
        if(!isPrime[i]) continue;

        for(int j = i * i; j < n + 1; j += i)
        {
            ifPrime[j] = false;
        }
    }

        return 0;
}

 

---

 

6. 1부터 n까지 k의 배수의 개수

1부터 30까지 8의 배수 ⇒ 8, 16, 24 ⇒ 3개

1부터 n까지 k의 배수 ⇒ n / k 개

 

 

---

 

7. n!에 곱해져 있는 소수 k의 개수

팩토리얼이란?  =>  5! = 1 * 2 * 3 * 4 * 5  로 표현한 것.

1. 기본형

10!에 2가 몇개나 있을까?

 

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10

 

1 2 3 4 5 6 7 8 9 10

0 1 0 2 0 1 0 3 0 1     <= 해당 수에 들어있는 2의 개수

 

int main()
{
    int cnt = 0;
    for(int i = 1; i < n + 1; i++)
    {
        while(i % 2 == 0)
        {
                cnt++;
                i /= 2;
        }
    }

    cout << cnt;

    return 0;
}

 

하지만 위 방법은 n이 충분히 작은 경우에만 가능하다.

 

2. 최적화

 

10!의 예시를 다시 한번 봐보자

 

int main()
{
    int n;
    cin >> n;

    int cnt = 0;
    for(int i = n; i < 11; i *= n)
    {
        cnt += 10 / i;
    }

    cout << cnt;

    return 0;
}

 

 

 

---

 

+ 모듈러의 성질

1. 모듈러는 분배법칙이 성립한다.
   • (a + b) % 3 == (a % 3) + (b % 3)
   • ex) (10 + 20) % 3 = (10 % 3) + (20 % 3)
   • (a * b) % 3 == (a % 3) * (b % 3)
   • (a - b) % 3 == (a % 3) - (b % 3)
   나눗셈을 제외한 사칙연산에서는 먼저 MOD를 계산하여도 상관이 없다.
2. 모듈러를 사용하여 순환형을 만들 수 있다.

for(int i = 0; i < 1000; i++)
{
	cout << i % 5 << '\n';
}

/*
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 ....
계속해서 반복되는 수가 나오게 됨.
*/