roose's blog

How to implement Erathostenes' sieve in O(sqrt(N)) ?
By roose, 12 years ago, In English

How to implement Erathostenes' sieve in O(sqrt(N)) thanks in advance.

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it

Where did you see, that it's possible? I now, that Erathostenes' sieve works in O(nloglog(n)). O(log(log(n))) was my mistake :D. (Sorry for my poor english :( )

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

It can be implemented in O(n) time, but not in O(sqrt(N)), it's fairy tale.

→ Reply