'PrimeNumber' 태그의 글 목록 — Archive

PrimeNumber

Computer Science/Data Structures & Algorithms

[Algorithms] Eratosthenes' Sieve | 에라토스테네스의 체

Eratosthenes' Sieve 에라토스테네스의 체 * 소수 (Prime Number) : 약수가 1과 자기 자신만 존재하는 자연수 * 합성수 (Composite Number) : 소수가 아닌 수 * 통상적으로, 1은 소수가 아닌것으로 정의한다. - 2 이상의 자연수 n이 소수인지를 Θ(n) 시간에 찾아낼 수 있는 알고리즘이다. (소수 판별을 Bruteforcing 방법으로 찾아낼 경우, Θ(n2) 시간이 소요된다.) - n이 소수인지를 판별하기 위해, 먼저 2Pin 인 소수 Pi들을 Bruteforcing하여 찾아낸 다음, 2 이상, n 이하의 수들 중 Pi의..