Need not to know

모두 메리 크리스마스! ▣ 정수론 시리즈 ─ 순서대로 읽으시는 걸 추천합니다. 1. 뫼비우스 함수와 디리클레 합성곱 2. Double Counting과 Harmonic Lemma 3. 곱셈적 함수 테이블 만들기 (현재 글) 4. Mertens Trick (xudyh's sieve) 「뫼비우스 함수와 디리클레 합성곱」 게시글에서 여러 곱셈적 함수들의 예시를 소개하였다. 본 글에서는, 곱셈적 함수들의 테이블을 만드는 코드들을 작성해 볼 것이다. 여기서 "함수의 테이블을 만든다"의 의미는 어떤 양의 정수 $N$과 함수 $f(n)$에 대해 $f(1)$, $f(2)$, $\cdots$, $f(N)$의 값을 모두 구한다는 의미이다. 양의 약수의 개수 $\tau(n)$ naive하게 $N$개의 값을 모두 구하면 $\..

몫 연산자(/)는 알다시피 컴퓨터공학에서 주로 정수끼리의 나눗셈을 나타낼 때 사용된다. 이름대로 나눗셈의 값을 그대로 반환하는 것이 아닌, '몫'을 반환하는 연산자다. 즉 수학에서 쓰는 '/'와 차이점이 있다(단, 파이썬의 '/'는 수학에서의 쓰임과 동일하다. 대신 파이썬에는 '//'이라는 몫 연산자가 따로 존재한다). 가우스 기호([ ])를 사용해서 말하자면, 정보과학에서 p/q는 수학에서의 $\left[\frac{p}{q}\right]$와 같다고 할 수 있다. 이 글에서는, 몫 연산자의 이러한 점을 이용한 팁을 알아볼 것이다. ※ 편의상 이후에 등장하는 미지수들은 모두 양수일 경우만 고려한다. floor, ceil, round 정수와 관련해서, 유명한(?) 함수들이 있다. 바로 floor(x), ce..