자주 쓰이는 알고리즘 모음 - 수학 편

※ 작성기준은 C/C++입니다.

 

---

 

10진수 n의 k진수 구하기

string get_K_number(int n, int k) {
    string answer = "";

    while(n)
    {
        answer.push_back(n%k + '0');
        n /= k;
    }

    reverse(answer.begin(), answer.end());

    return answer;
}

 

 

소수 판별하기

방법 1) 배열에 기록해두는 방법

bool numbers[1000] = {true,}; // 모두 true로 초기화

numbers[0] = false;
numbers[1] = false;

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

 

방법 2) 제곱근을 이용한 방법

bool isPrime(int n)
{
    if (n == 0 || n == 1)
        return false;

    int squareRoot = sqrt(n);

    for (int i = 2; i <= squareRoot; ++i)
        if (n%i == 0)
            return false;

    return true;
}

 

약수 구하기

vector<int> get_Divisors(int n) {
    vector<int> answer;

    answer.push_back(1);

    for(int i = 2; i <= n/2; i++)
        if(n%i == 0)
            answer.push_back(i);

    answer.push_back(n);

    return answer;
}

 

 

최대 공약수(유클리드)

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

 

 

최소 공배수 - 최대 공약수 알고리즘 필요!

int get_lcm(int a, int b) {
    return a*b/get_gcd(a, b);
}