특정 수가 소수인지는 O(root(n))으로 가능할탠데 이걸 말씀하시는건가요?
범위로 소수를 판단하는것중에 빠른건 에라토스테네스밖엔 모르겠네요.
1990번 - 소수인팰린드롬
N의 최대가 1억이지만, 가능한 모양은 최대 $sqrt{N}$개밖에 되지 않습니다.
따라서 가능한 모든 펠린드롬을 만들어두고, 범위 조건을 만족하는 수들만을 모아줍니다.
이후 각각의 수들에 대하여 소수인지 검사를 하는데, 이 소수 판별법 역시 최대 $sqrt(N)$만큼을 경과하게 됩니다.
따라서 이 둘을 곱하게 되면 O(N)의 시간복잡도로 이 문제를 해결할 수 있습니다.
에라토스테네스의 체는 범위를 거르는 것에는 매우 빠르나, 이 시간복잡도는 O( N lnN + Nψ ) (여기서 ψ는 1 이하의 상수라 생각하시면 됩니다.) 가 걸린다고 알려져있습니다.
따라서 일반적으로 시간복잡도를 O(NlogN)으로 생각하셔도 시간 계산에는 큰 무리가 없습니다. (N은 당연히 범위라는걸 이해하시리라 생각합니다.)
에라토스테네스의 체를 통해 인덱스를 방문하는 횟수를 세서 출력해보시면, 어느정도로 횟수가 걸리나를 예측할 수 있습니다. 가끔은 긴가민가할떄 이걸 직접 출력해서 몇번이나 세는지 보면 좋죠...
에라토스테네스 체 알고리즘의 시간복잡도는 O(n log(log n))입니다. n log n보다도 훨씬 빠릅니다.
간단하게, 우선, 1/n + 2/n + ... n/n을 1/x의 연속함수라하고 적분하면 log n이 되는데, 체에 의해 걸러지는 것들은 더해지지 않아서 log(log n)이 됩니다.
루트(n) 알고리즘을 쓰기보다는, n의 범위를 잘 파악하여 에라토스테네스 체 알고리즘을 사용하는 걸 권장드립니다.
예를 들어 x가 소수인지 알아보려면, 루트(x)까지 에라토스테네스 체 알고리즘으로 모든 소수를 구해놓은 뒤, x를 구해놓은 소수들로 다 나눠보다가, 안 나누어진다면 소수라고 판정할 수 있죠.
\(\sqrt{n}\) 은 $ 말고 \ (와 \ )로 사용할 수 있습니다. (\와 (사이에 공백없이)
댓글을 작성하려면 로그인해야 합니다.
jormal 9년 전
팰린드롬을 이미 만든 상태에서 소수를 확인하는게 빠르다는걸 알게되어서 문제를 푸는중에
100%에서 시간초과가 떠버리네요...
체거르기가 시간잡아먹는거같은데 다른 방법 없을까요..
아니면 코드에서 문제가 있나요..?