에라토스테네스의 채

[1456] 거의 소수(C++)

문제 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 입력 첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. 출력 첫째 줄에 총 몇 개가 있는지 출력한다. 해결 방법 에라토스테네스의 채를 이용한 문제이다. 에라토스테네스의 채는 소수를 쉽게 찾는 방법인데, 채에다가 찌꺼기를 걸러내는 것처럼 소수를 찾아나가는 것이 아니라 소수가 아닌 애들을 걸러내는 방식이다. 이렇게 소수 여부를 저장했으면 각 소수의 2배수, 3배수.... 중에 A보다 크거나 같고 B보다 작거나 같은 수를 찾으면 된다. 이때 주의해야 할 부분이 있는데 while(num