[알고리즘] 함수

1. 가설 적용 코드 (C++)

typedef unsigned long long ll;

/*
*  input : ll input (정수)
*  output : int (1 or 0)
*  unsigned long long 형태의 정수를 넣으면 해당 수가 소수인지 여부를 알려준다.
*  소수 판별 custom 버전
*/
int is_prime_number_custom(ll input)
{
    if (input < 2) {
        return 0;
    }

    for (ll j = 2; j <= (ll)(input / j); j++)
    {
        if (input % j == 0)
        {
            return 0;
        }
    }

    return 1;
}

 

2. 가설 적용 코드 (Python)

def func1(input):
    if input < 2:
    	return 0
    for j in range(2, int(input/j)+1):
        if input % j == 0:
            return 0
    return 1

 

3. 에라토스테네스의 체 (c++)

/*
* input : int m
* output : 1부터 m까지의 소수 여부를 sizeof(bool) * (m+1)크기의 bool * 형태로 반환한다.
* 사용 시 반환된 bool array에 해당 자연수를 조회하면 소수 여부를 알 수 있다.
*/
bool *Sieve_of_Eratosthenes(int m) {
    bool* arr = new bool[m + 1];

    memset(arr, 1, sizeof(bool) * (m+1));
    arr[0] = false;
    arr[0] = false;

    for (int i = 2; i < m + 1; i++) {
        if (arr[i] == true) {
            for (int j = i * 2; j < m + 1; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}

 

4. 최소 공배수, 최대 공약수

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

int func_2609_lcm(int a, int b) {
    return (a * b) / func_2609_gcd(a, b);
}