Computer science/알고리즘

[LeetCode] 204. Count Primes

Count the number of prime numbers less than a non-negative number, n. Example: Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. 해당 문제를 풀 때, 처음에는 단순하게 접근하여 이중 for문으로 구현하려고 하였으나 Time Limit Exceeded 제약에 걸려버려 통과를 할 수 없는 상황이 발생했습니다. 해당 문제를 고민하다가 분명 시간복잡도를 줄이기 위한 좋은 아이디어가 존재할거라 생각하여 리서치한 결과 에라토스테네스의 체라는 소수 판별 방법이 존재하는 것을 알게 되었습니다. 접근 방법은 아래와 같습니다. 2부터 소수를 구..