반응형 에라토스테네스의 체1 [백준/C++] 소수의 연속합 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때, N까지의 소수를 구한 다음에 투 포인터로 연속합을 계산하면 되겠다고 생각했다. 하지만 여기서 간과한 점이 소수를 구하는데 걸리는 시간이었다. 처음에는 2~4,000,000까지 하나씩 전부 소수인지 검사했다.그렇기 때문에 시간복잡도가 O(N^3/2)이 됐다. 그래서 이 시간을 줄이기 위해 예전에 에라토스테네스의 체를 이용했다.에라토스테네스의 체를 이용하면 (n/1 ~ n/n)을 전부 더한 시간복잡도로 O(NlogN)으로 소수들을 구할 수 있다. 그래서 에라토스테네스의 체로 소수들을 구해 빠르.. 2024. 5. 4. 이전 1 다음 반응형