아마 ps 갤 대부분 이용자는 이 문제를 풀었거나

들어보기만 했지 안 푼 사람도 있을거임.

그래서 풀이를 해보기로 했음.

메모장에 적은거 복붙해서 적는거라 정확하진 않을수도 있음.


풀이


1.

일단 에라토스테네스의 체를 사용해서 1부터 100만까지 소수를 구함.

이걸 구현하기 위해 a라는 백터를 사용하고 모든수를 소수로 가정함.

1은 소수가 아니기에 a[1]을 false로 설정하고 소수가 아닌 수를 걸러내기 위해 배수를 소수에서 제외 시킴.

2.

이제 min부터 max 까지의 범위에서 각 소수 I의 제곱과 그 배수들을 체크하는데

이걸 ck라는 벡터를 사용해서 해결함.

ck의 각 인덱스는 min과 max 사이의 숫자를 나타냄.

소수 I의 제곱은 I*I 이므로 max이상의 제곱근 이상의 수는 고려할 필요가 없음.

3.

이제 각 소수 I에 대해서 min보다 크거나 같은 수 중에서 i의 제곱보다

크거나 같고 max보다 작은 수들을 찾음.

이를 위해 min / square에서 시작하여

(min % square != 0 ? 1 : 0)을 더해줌.

이제 이렇게 하면 min과 square의 곱이 min 이상으로 만들어주게함.

4.

이제 찾은 수들을 ck에 체크함.

체크 안 된 수는 소수임.

5. 마지막으로 ck에서 체크되지 않은 수의 개수를 세고 출력함.


시간 복잡도


1. 에라토스테네스의 체를 사용하여 소수를 구하는 부분

대략 O(NloglogN)의 시간이 소요될거임.

여기서의 N은 범위내의 숫자의 개수임.

2. 제곱수와 그 배수는 체크하는 부분

이 부분은 대략 O(sqrt(max))의 시간이 소요될거임.

왜냐면 소수 I의 제곱은 I*I니까 max이상의 제곱근은 고려할 필요가 없음.

3. 체크된 수의 개수를 세는 부분

O(max-min)의 시간이 소요될거임.


따라서 전체적인 시간복잡도는 O(NloglogN + sqrt(max) + max - min)이고

범위가 100만 이하이므로 대략적으로 O(NloglogN + sqrt(max))정도의 시간복잡도가 될거임.