거의 소수 - 1456. 시간복잡도

1456번: 거의 소수 1456번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 거의 소수 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 7358 1810 1232 23.674% 문제 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

입력 첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. 출력 첫째 줄에 총 몇 개가 있는지 출력한다.

제한 1 ≤ A ... www.acmicpc.net 문제에 대한 풀이는 대부분 비슷한것 같으니, 따로 서술하지 않겠다. 처음에 sqrt(B)까지 Sieve of eratosthenes 알고리즘을 돌린다.

돌린 후, 1부터 sqrt(B)까지 순회를 돌리며 소수만 고려해준다. 어떤 분의 말에 의하면 1부터 B까지의 소수 개수는 대충 sqrt(B)개로 생...