정수 알고리즘들

최대공약수 ( Greatest common divisor ) 구하기

최소공배수 ( Least Common Multiplicator )

int GCD(int a, int b) {
    if (a == b) return a;
    if (a > b) return GCD(a - b, b);
    else return GCD(a, b - a);
}
 
int LCM(int a, int b) {
    return (a*b) / GCD(a, b);
}

----------

소인수 분해 하기 ( Prime Factorization )

- 시간 복잡도는 O(sqrt(N))

void primefactors(int n) {
    // 2를 전부 제거해서 홀수를 만든다.
    while (n % 2 == 0) {
        cout << 2 << " ";
        n /= 2;
    }
    // 남은 것을 3 ~ 루트n까지 하나씩 나눠본다. 여러개일 수도
    // 있으니 전부 나눠 본다.
    for (int i = 3; i*i <= n; i = i + 2) {
        while (n%i == 0) {
            cout << i << " ";
            n /= i;
        }
    }
 
    // 소수라면 아직 나눠지지 않은 상태이다.
    if (n > 2) {
        cout << n;
    }
 
    cout << endl;
}

** preprocessing을 이용한 log(N) 시간에 구하기

// Calculating SPF (Smallest Prime Factor) for every
// number till MAXN.
// Time Complexity : O(nloglogn)
void sieve()
{
    spf[1] = 1;
    for (int i=2; i<MAXN; i++)
 
        // marking smallest prime factor for every
        // number to be itself.
        spf[i] = i;
 
    // separately marking spf for every even
    // number as 2
    for (int i=4; i<MAXN; i+=2)
        spf[i] = 2;
 
    for (int i=3; i*i<MAXN; i++)
    {
        // checking if i is prime
        if (spf[i] == i)
        {
            // marking SPF for all numbers divisible by i
            for (int j=i*i; j<MAXN; j+=i)
 
                // marking spf[j] if it is not 
                // previously marked
                if (spf[j]==j)
                    spf[j] = i;
        }
    }
}
 
// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
vector<int> getFactorization(int x)
{
    vector<int> ret;
    while (x != 1)
    {
        ret.push_back(spf[x]);
        x = x / spf[x];
    }
    return ret;
}

----------

소수 구하기 ( 에라토스테네스의 체 )

vector<bool> primes(int n) {
    vector<bool> isprime(n + 1, true);
    
    // 2에서부터 하나씩 트루인 것들의 배수를 싹 지운다.
    for (int i = 2; i * i <= n; i++) {
        if (isprime[i] == true) {
            for (int j = i * 2; j <= n; j++) {
                isprime[j] = false;
            }
        }
    }
 
    // 남는게 답.
    return isprime;
}

----------

나뉘는지 아는 방법

2 : 끝자리가 2로 나뉜다

3 : 모든 자릿수의 합이 3으로 나뉜다.

4 : 끝 두자리가 4로 나뉜다

5: 끝자리가 5나 0이다.

6 : 2로 나뉘고 3으로 나뉜다.

7 : 끝자리를 두배 해서 나머지 자릿수 숫자에서 뺀다. 적당히 적어질 떄 까지 재귀적으로 반복한다.

8 : 끝 세자리가 8로 나뉜다.

9 : 자릿수의 합이 9의 배수다.

------------