jshyun912   5달 전

제 얉은 지식으론 즉석으로 소수 판별하는거보다 에라토스테네스의 체가 시간복잡도가 더 빠르다고 알고 있어서 체를 썼는데 엄청 느리더라구요.

근데 그냥 즉석에서 소수판별시키는걸로 하니까 시간이 확 빨라지는데...

체를 쓰는게 빠르겠다 아니면 그냥 즉석으로 판단하는게 빠르겠다를 어떻게 구별을 할 수 있을까요? 일단 둘 다 해보고 빠른걸 넣는다던가...?

slah007   5달 전

체는 1 ~ N 범위의 수가 각각 소수인지 아닌지를 O(N log log N)에 판별합니다.

일반적인 sqrt(N) 소수 판정을 1 ~ N에 대해 모두 진행하면 N^(3/2) 정도라 대충 N^1에 가까운 체보다 훨씬 느리지만, 적은 개수만 판정한다면 당연히 sqrt(N)이 더 빠릅니다.

댓글을 작성하려면 로그인해야 합니다.