에라토스테네스의 체는 $O(nlog(logn))$의 시간 복잡도를 가지는 알고리즘으로, 효율적으로 소수(Prime Number)를 구할 수 있다. 소수: 1과 자기 자신 만을 약수로 가지는 수 아이디어는 간단하다. 자연수 N이 있을 때, N의 배수는 소수가 아니다. 소수는 1과 자기 자신만을 약수로 가지는데, N의 배수는 N을 약수로 가지기 때문이다. 소수의 정의를 생각해 보면 당연한 이야기이다. 1 ~ 100까지의 수가 있는 표를 만들자. 그리고 만약 소수가 아니라면 표에서 값을 지운다. 0과 1은 소수가 아니다. 0 1 2 3 4 5 6 7 8 ... 2는 소수이다. 하지만 2의 배수는 소수가 아니다. 따라서 4, 6, 8 ... 등은 지운다. 0 1 2 3 4 5 6 7 8 ... 3은 소수이다. ..
PySet은 아주 유용한 자료구조이다. 이를 Go로 Go스럽게 구현하기 위해 CPython의 소스코드와 golang 소스코드를 살펴보았다. set과 map이 뒤에서 어떻게 작동하는지를 살펴보고 가장 합리적인 방법으로 집합을 구현해보려 한다. 문제 Python에는 집합이라는 아주 유용한 구조가 있다. set 객체는 크게 2가지 역할이 있는데, 중복 값을 제거하는 것과 빠르게 값을 탐색하는 것이다. n = [1, 3, 3, 5, 6, 3, 8] n = set(n) print(n) # {1, 3, 5, 6, 8} has_three = (3 in n) print(has_three) # True 하지만 Go는 set을 제공하지 않는다. 따라서 set과 유사하게 작동하는 객체를 만들어보려 한다. 그런데 Go를 곁들..