Illie

서론 알고리즘 문제를 풀다가 소수 구하는 문제를 만났다 for문으로 1부터 해당 숫자까지 돌면서 나머지가 있는지 없는지 확인을 했더니 시간 복잡도에서 통과하지 못했다 구글 선생의 도움을 받아, 제곱근을 성질을 사용하면 된다고 한다 O(루트 n) function get_prime(num) { for (let i = 2; i * i < num; i+=1) { num % i // 어쩌고 저쩌고 로직 추가 } } 근데...!! 오늘 알고리즘을 공부하다가 에리토스테네스의 체 라는 것을 알게되었고 O(n log log n) 복잡도가 걸리고 소수 문제는 무조건 에리토스테네스의 체로 풀면 된다고 한다... 끄악! 본론 소수의 경우 true로 나오고, 소수가 아닌 경우 false가 나온다 로직은 아래의 식을 활용하여 변..