에라토스테네스의 체에서 제곱근 까지만 루프를 도는 이유

intro 에라토스테네스의 체로 소수를 판별하는 코드를 보면, n의 제곱근까지만 루프를 돌면서 index의 배수들을 소수목록에서 지운다. 보통 쉽게 한두줄로 왜 그런지 설명을 해놓았는데, 나는 이해가 잘 안가서 오래 생각을 해봤다. 아하! 그런거군! 자, 50까지의 수에서 2의 배수를 소수탈락 시켜보자. 2 * 2 / 2 * 3 / 2 * 4 ....... 2 * 25까지 지운다. 2의 배수만 지웠다(물론 2는 소수!) 이제 3의 배수를 지워보자. 3 * 2 / 3 * 3 / 3 * 4 / 3 * 5 ... 3 * 16까지! 3의 배수를 지웠다 4의 배수는 건너 뛰고, 5의 배수를 탈락 시켜보자! 5 * 2 / 5 * 3 / 5 * 4 / 5 * 5/ ... 5 * 10까지! 5의 배수를 지웠다 6의...

트리의 순회 (pre, in, post order)

이진 트리를 순회하는 3가지 방식에 대해 알아보자. 트리의 모양 먼저 순회할 트리의 모양은 다음과 같다. from collections import deque class Node: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right class Tree: L, R = 'left', 'right' def __init__(self, rootVal): self.rootNode = Node(rootVal) def insert(self, val): emptyNode = self.findEmptyNode() if emptyNode[1] == Tree.L: emptyNode[0]...

알고리즘을 위한 파이썬 – Collections

참고자료 OrderedDict 파이썬에서 dictionary는 기본적으로 hashmap으로 만들어졌기 때문에 저장되는 순서를 고려하지 않는다. 그래서 dic.items() 함수가 항상 같은 순서의 배열을 리턴한다고 보장 할 수 없다(고한다..). 내부적으로 linked list를 사용해서 순서를 유지함 from collections import OrderedDict a = OrderedDict([['a', 1], ['b', 2], ['c', 3]]) print(a) # OrderedDict([('a', 1), ('b', 2), ('c', 3)]) 나중에 유용하게 쓰일 것 같다. Counter 원소들의 개수를 세준다. 매~우 유용하다. from collections import Counter items =...

알고리즘을 위한 파이썬 – 순열/조합

Permutations 순열, 줄세우는 여러가지 경우의 수 from itertools import permutations items = [1, 2, 3] perms = permutations(items, 2) print(list(perms)) # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)] Combinations 조합, 주머니에서 n개를 뽑아서 나오는 모든 경우의수 from itertools import combinations items = [1, 2, 3] combs = combinations(items, 2) print(list(combs)) # [(1, 2), (1, 3), (2, 3)] Product 곱집합 from itertools import...

알고리즘을 위한 파이썬 – Dictionary

참고자료 키 중복 dic = { 'a': 2, 'a': 5 } print(dic) # {'a': 5} 새로운 key-value 추가 dic = { 'a': 2 } dic['b'] = 100 print(dic) # {'a': 2, 'b': 100} Array to Dictionary list = [('a', 10), ('b', 20)] dic = dict(list) print(dic) # {'a': 10, 'b': 20} list = [(10, 'a'), (20, 'b')] dic = dict(list) print(dic) # {10: 'a', 20: 'b'} 복사 얕은복사 a = {'alice': [1, 2, 3], 'bob': 20, 'tony': 15, 'suzy': 30} b = a.copy()...

알고리즘을 위한 파이썬 – Array

Range reverse a = [1, 23, 5, 6, 7] for i in range(len(a), -1, -1) : print(i) step for i in range(0, 20, 2) : print(i) # 0 2 4 6 ~ 20 test = [4, 3, 5, 11, 5] for i in range(20, 0, -2) : print(i) # 20 18 16 14 ... 2 다만, 아래와 같은 경우에는 루프를 (당연히) 안돈다 for i in range(10, 20, -2): print(i) Array to String list1 = ['a', 'b', 'c'] str1 = ''.join(list1) 근데, 숫자는 안의 내용물을 문자로 바꿔주고 join해야한다 list1 = [1, 2, 3] str1...

에라토스체네스의 체

이게뭐야?

위키피디아

쉽게 말하면, 소수를 찾는 방법이다. 소수라 함은 그 수의 약수가 1과 자기 자신만을 가지는거다.

파이썬 구현

def prime_list(n):
# 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
n = n + 1 # 이렇게 하면 소수목록에서 조회할때 -1 안해줘도 된다
sieve = [True] * n

# n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i]: # i가 소수인 경우
for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
sieve[j] = False

# 소수 목록 산출
return sieve

어따씀?