Блог пользователя roose

Автор roose, 12 лет назад, По-английски

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

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

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 :( )

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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