반응형 소수구하기1 #1456 거의 소수 이번 문제는 소수를 구하는 문제입니다. 난이도는 Silver I 정도로 평가됩니다. 소수를 구하는 방법은 여러가지가 있는데, 일단은 2부터 n까지 숫자중 소수를 구하는 것이라면 \(O(n \sqrt {n} )\) 정도의 알고리즘으로 구할 수 있습니다. 에라토스테네스의 체를 이용하면, 메모리 공간이 좀 들겠지만, 가장 준수한 효율로 소수를 구할 수 있습니다. 거의 소수는 소수 \(p\)에 대해서 \(p^N\) 형태로 표현되는 수를 말합니다. 소수 자체는 거의 소수가 아니므로 실제로 주어진 범위안에서 구할 소수는 \( \sqrt {n} \) 범위입니다. 주어진 범위가 a ~ b 까지이므로 2 ~ b 까지의 거의 소수 개수를 구한 후 2 ~ a-1 까지의 거의 소수 개수를 빼주면 됩니다. 숫자의 범위가 \(1.. 2022. 8. 11. 이전 1 다음 728x90