루트 n까지만 검사해도 소수를 판별할 수 있습니다. 만일 루트 n을 넘는 약수가 존재한다면, 그 약수로 나눈 몫은 루트 n보다 작은 약수일 테니 이미 이전에 걸러졌어야 하니까요.
2581번 - 소수
is_prime 함수의 복잡도가 최악의 경우에 O(n)이니 오래 걸릴수밖에 없긴 해요.
대충 n이하의 소수 갯수는 n/logn 정도에 근사하는데요.
생각보다 djs님 코드가 오래 걸리지 않는 이유가
1부터 10000까지만 전수조사하면 되는 것도 있고요.
소수가 아닌 경우에 최대 O(root(n))만큼만 돌면 됩니다.
이걸 잘 풀어보면 대충..
(n-n/logn)*root(n) + n^2/logn 즈음 되는데요.
앞의 것은 대충 O(n루트n)정도. 뒤의 것은 O(n^2/logn)이라고 생각하면 되니까 실제 시간 복잡도는 O(n^2)가 아니라
O(n^2/logn) 정도고요.
소수가 아닌 경우에는 최악의 경우에나 루트 n이지.
그렇지 않은 경우에는 더 적은 루프로 끝나버리죠.. 자세한 건 소수 정리 참고해 보세요.
답변 주신 분들 너무 고마워요!!!
댓글을 작성하려면 로그인해야 합니다.
djswpsk1024 5년 전