'소수' 태그의 글 목록

소수를 구할 때 쓰는 알고리즘 중에서, 에라토스테네스의 체 알고리즘이 있습니다. 제가 ps를 하면서 상당히 많이 썻던 것인데요. 결론부터 말씀드리겠습니다. [1,n]까지 해당 알고리즘을 이용해서 훑는 경우에, 시간 복잡도는 O(nlog(logn))입니다. 생각보다 상당히 빠르게 동작한다는 것을 알 수 있어요. [1,14]의 범위에 있는 자연수가 소수인지 아닌지 빠르게 훑어봅시다. 하늘색은, 아직 visit를 하지 않았다는 의미입니다. 일단 이것이 무엇을 의미하는지 추후에 보도록 합시다. 먼저, 1은 소수가 아니므로, 노란색으로 표시를 합니다. 다음에, 2를 봅시다. 2는 하늘색으로 표시가 되어 있으므로, 방문한 녀석이 아닙니다. 그러면 여기서 우리는, 2를 제외한, 2의 배수들을 모두 제거를 할 건데요...