[정수론] [정리 필요]number theory

소수(prime number)

 

소수는 양의 약수가 1과 자기 자신 두 개 뿐인 자연수를 의미한다.

 

소수의 반대: 합성수(composite number): 세 개 이상의 양의 약수를 갖는 자연수

 

가장 단순한 소수판별:

     2 부터 n -1 까지 모든 수를 순회, n의 약수가 있는지 확인

    (합성수의 성질에 따라 sqrt(n)이하 까지 순회하도록 최적화 가능)

    (비트 수에 따라 수행시간이 증가 => 비트 수가 하나 증가 => 수행시간 두배 => 지수시간)

    (1, 2, 3 제외 한 모든 소수는 6k +- 1 형태임을 이용할 수 도 있다.)

     (2 를 제외하면 모든 짝수는 소수가 아니다.)

bool isPrime(int n)
{
    if(n <= 1) return false;
    if(n == 2) return true;
    if(n%2 == 0) return false;
    int sqrtn = int(sqrt(n));
    for(int i = 3; i < sqrtn; i+=2)
        if(n%i == 0) return false;
    return true;
}

 

소인수 분해(prime factorization): 

    한 합성수를 소수들의 곱으로 표현하는 방법을 찾는것

    2부터 시작해 n의 소인수가 될 수 있는 수들을 하나하나 순회.

    n의 약수를 찾을 때 마다 n을 이 숫자로 나눈다.

    최적화 :입력의 최대값 max에 대하여 sqrt(max)까지의 소수들을 미리 찾아두고

              [2, sqrt(n)]의 범위의 모든 정수 대신 소수들로만 나눔.

vector<int> factorSimple(int n)
{
    vector<int> ret;
    int sqrtn = int(sqrt(n));
    for (int div = 2; div <= sqrtn; div++)
        while(n%div==0)
        {
            n /= div;
            ret.push_back(div);
        }
    if(n>1) ret.push_back(n);
    return ret;
}

 

에라토스테네스의 체(sieve of Eratosthenes):

    주어진 n이하의 소수들을 모두 찾아냄.

    먼저 2의 배수들을 지움.

    지워지지 않은 수 중 첫번째 수 3의 배수들을 다 지움

    다음으로 5를 지움...

    

    지우고 나온 남은 수들 첫번째의 배수를 다 지우면

    작업을 다 한 뒤 남은 것들은 결국 소수가 된다.

 

bool isPrime[INT32_MAX];
int n;
 
void eratosthenes()
{
    memset(isPrime, 1, sizeof isPrime);
    isPrime[0] = isPrime[1] = false;
    int sqrtn = int(sqrt(n));
    for(int i = 2; i <= sqrtn; i++)
        if(isPrime[i])
            for(int j = i*i; j <= n; j+=i)
               isPrime[j] = false;
}
 

에라스테네스의 체의 문제점은 메모리 사용량이다.

많은 수에 대해 수행해야 할 때는 짝수를 별도로 처리해서 필요한 배열의 크기를 

절반으로 줄여야한다.

또는 비트마스크 기법을 이용하여 최적화한다.

 

에라토스테네스의 체를 이용한 소인수 분해

 

 

int minFactor[INT32_MAX];
int n;
void eratosthenes()
{
    for(int i = 2; i < n; i++) minFactor[i] = i;
 
    minFactor[0] = minFactor[1] = -1;
 
    int sqrtn = int(sqrt(n));
 
    for(int i = 2; i <= sqrtn; i++)
        if(minFactor[i] == i)
            for(int j = i*i; j <= n; j+=i)
                    if(minFactor[j] == j)
                        minFactor[j] = i;
}
 
vector<int> factor()
{
    vector<int> ret;
    while(n > 1)
    {
        n/=minFactor[n];
        ret.push_back(minFactor[n]);
    }
    return ret;
}

 

유클리드 알고리즘

최대 공약수를 구하는 알고리즘.

최대 공약수를 g라고 하자

 

A = a*g , B = b*g

 

A - B = (a-b)*g

 

두 수의 뺀 값은 최대 공약수를 유지하며

이는 계속해서 뺄셈하면 결국 최대 공약수를 얻을 수 있음을 의미한다.

 

하지만 엄청 큰 수와의 최대 공약수를 구하는 문제는 위와 같이 해결하면

시간이 꽤 걸리게 된다.

 

이를 해결하는 방법은 나머지를 취하는 것이다.

(작은수의 배수를 한꺼번에 빼는것) 

int gcd(int a, int b) 
{
    if(a == 0) return b;
    else gcd(b%a, a);
}

모듈라 연산(modular arithmetic)

모듈라 연산이란, 모듈로 M에 도달하면 다시 0으로 돌아가는 정수들을 가지고 하는 연산이다.

모듈로 연산에서 모든 정수는 M으로 나눈 나머지로 표현된다.(24시간 시계)

 

큰 정수를 다뤄야 하는 문제에서 자주 쓰임

 

모듈라 덧셈, 뺄셈, 곱셈

 

a%m = a'   ... a = xm + a'

b%m = b'  ... b = xm + b'

 

 

(a+b) =(x + y)*m + (a' + b')

(a+b)%m = (a'+b')%m

(a-b)%m = (a' - b' + m) %m ... 음수가 될 수 있기 때문에 

(a*b)%m = (a'*b')%m

 

****모듈라 나눗셈**** 따로 정리 필요

 

나눗셈에 대해서는 일반적인 공식이 성립하지 않는다.

 

모듈라 연산에서의 나눗셈 a/b는 b로 나누는 대신 

b의 곱셈 역원(multiplicative inverse)을 곱하는 방식으로 이루어짐.

(f 와 어떤 수 a가 주어질 때 f(a, b) = f(b, a) = e인 b가 유일하면 b는 a의 역원)

(f(a,b)의 항등원 e 는 f(x, e) = x를 항상 보장하는 수)

 

곱셈 역원은 항상 존재하는게 아니라 b와 m이 서로소일 때만 존재

모듈라 연산은 정수만을 다루기 때문에 나누어 떨어지지 않으면 나눌 수 없음.

 

따라서 m이 소수이면 다음과 같다. (페르마의 소정리)

 

modInv(b,m) = b^(m-2)%m

(a/b)%m= (a*modInv(b,m))%m

 

m이 소수가 아닌경우 다음과 같인 식을 만족하는 A를 찾으면 된다.

(디오판틴 방정식, 확장 유클리드 알고리즘)

A*b + B*M ≡ 1 (mod M)

 

확장 유클리드 알고리즘(Extended Euclidean algorithm)

 

유클리드 알고리즘은 한 수에서 다른 수를 빼는 과정을 반복하기 때문에.

gcd(p,q)을 수행하는 도중에 출현하는 모든 수는 p, q의 가중치 합인

ap + bq로 쓸 수 있다. 

 

ex gcd(6, 15) = gcd(9, 6) = gcd(3,6) = gcd(3,3) = gcd(0,3) = 3

 

gcd(9, 6) 에서 9 = -1*6 + 1*15

gcd(3,6) 에서  3 = 1*9 + -1*6 = -2*6 + 1*15

 

따라서 

 

gcd(p, q) = a*p + b*q

 

이때 유클리드 알고리즘에 코드를 적절히 추가해 최대 공약수와 함께

a,b를 반환할 수 있다. 이와 같은 알고리즘을 확장 유클리드 알고리즘이라한다.

 

중국인 나머지 정리

오래된 중국 수학책에서 처음 등장했다고해서 이름이 중국인 나머지 정리이다.

 

n개의 사과를 세명에서  같은 개수 -> 두개남음

한명 더불러서 네명에서 같은 개수 -> 세개남음

한명 더불러서 다섯명에서 같은 개수-> 한개남음

최소 n은 얼마인가?

 

위와 같은 형태의 문제를 풀 수 있게하는 정리이다.(연립 합동식)

중국인 나머지 정리를 이용 -> 확장 유클리드 알고리즘을 통해 답을 구함.

 

뤼카의 정리

 

모듈라 연산을 이용한 이항 계수(n r)을 빠르게 구할 수 있게 해주는 정리.

모듈라 연산을 이용하지 않을 경우엔 계산하기 어려울 정도로 큰 n 과 r에 대해

이항 계수를 계산할 수 있도록 해줌

 

 

-알고리즘 문제해결전략 516p