쉬어가는 코너: 기초수학!

제로베이스 데이터 취업 스쿨 2주차 스터디노트 1호

수학이 어떻게 쉬어가는 코너냐구요?
행복하려면 어쩔 수 없잖아요, 자기합리화 하는 거죠.
같이 말해봐요, 수학은 즐겁...웩...즐겁다!

소인수 알고리즘

어떤 수를 소인수분해 할 때엔,
그 수의 제곱근까지만 확인하면 된다.

에라스토테네스의 체

범위에서 합성수를 지워 소수를 구하는 방법

def get_primes(num):
    result = []
    sieve = [False] * 2 + [True] * (num - 1)
    for idx in range(2, int(sqrt(num)) + 1): # 위의 소인수 알고리즘 사용
        if sieve[idx]:
            j = 2
            while idx * j < num:
                sieve[idx * j] = False
                j += 1
    for idx, is_prime in enumerate(sieve):
        if is_prime:
            result.append(idx)
    return result

A x B = L x G

두 수의 곱은
두 수의 최소공배수와 최대공약수의 곱과 같다.

유클리드 호제법

두 양의 정수 a, b에 대하여
a = bq + r이라 할 때
gcd(a, b) = gcd(b, r)

영어 표현

소수: prime number
소인수: prime factor
소인수분해: prime factorization
합성수: composite number
공약수: common divisor
최대공약수: greatest common divisor
공배수: common multiple
최소공배수: least common multiple