Aden_blizzard's blog

doubt in sieve in linear time
By Aden_blizzard, history, 4 years ago, In English

https://cp-algorithms.com/algebra/prime-sieve-linear.html in this code for sieve in linear time complexity what is the use of pr[j]<=lp[i]? is there any reason to write this as i tried many test case but it works fine without this ....is there any case where it fails?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Obviously it will work only number of operations will increase, for the same purpose of reducing runtime we have added that

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

It's still correct. You just loop more than you need so it is no longer O(n).

→ Reply