### shyam81295's blog

By shyam81295, history, 6 years ago,

Hello, guys,

I am still learning algorithms and implementing them. But, Sometimes I get stuck when asked about generating prime numbers in O(N) time complexity. Although, I have implemented Sieve of Eratosthenes, but I have read somewhere that, it requires O(N*log(logN)) or something like that. I find this algorithm as good one, but in some practice problems, we need to implement in O(N) time.

It would be nice if someone of you will guide me to generate prime numbers in O(N) time.

• +3

 » 6 years ago, # |   +4
•  » » 6 years ago, # ^ | ← Rev. 2 →   +16 Brief description in English.
•  » » » 6 years ago, # ^ |   0 I am sorry by mistake I downvoted you. Actually I liked your answer. I want to upvote but it's not getting changed :(
•  » » 2 years ago, # ^ | ← Rev. 2 →   0
 » 6 years ago, # |   +8 I don't think that you will find many (or any) problems in which regular sieve is not enough.
•  » » 6 years ago, # ^ |   0
•  » » » 6 years ago, # ^ |   +3 Well, I guess I underestimated SPOJ's crazy optimization problems once again.
•  » » » » 2 years ago, # ^ |   0 I clicked on your profile->submissions to see Haskell solutions. I feel cheated now.
 » 6 years ago, # |   0 It is well known that log(log(N))<=5 :)
 » 6 years ago, # | ← Rev. 2 →   0 One optimization in sieve for (int i = 4; i <= n; i += 2) { bad[i] = true; } for (int i = 3; i * i <= n; i += 2) for (int j = i * i; j <= n; j += i + i) bad[j] = true; UPD. Fixed
•  » » 6 years ago, # ^ |   +1 In the last "for" you can begin from j = i*i.
•  » » » 6 years ago, # ^ |   0 I can't, I must! Thanks :)
•  » » 6 years ago, # ^ |   0 I think sieve runs faster than this code.sieve — 4.05 syour code — 6.21 s
 » 6 years ago, # |   -23 so if you need to get all prime numbers <=n;do thisfor(i=10;i<=n;i++) { if(i%2!=0 && i%3!=0 && i%5!=0 &&i%7!=0) { then number is prime; }} keep in mind hat we are starting from 10...as we already know primes less than 10....we could write our code with if---else ......hope this helps.....ask if you have any doubt..
•  » » 6 years ago, # ^ |   +22
•  » » 6 years ago, # ^ |   -11 Hi, I have doubt.. how much time it'll take u to completely destroy my algorithms knowledge ?
•  » » » 6 years ago, # ^ |   -6 Then stop this method and go for sieve of Eratosthenes...
•  » » » » 6 years ago, # ^ |   -13 relax man,no matter how hard u try...u cannot destory which does not exist,
•  » » » » » 6 years ago, # ^ |   0 r u good at algos then??????.....raing???
•  » » » » » » 6 years ago, # ^ |   0 I mean say I know 0 about algorithms .. so u cannot destory my knowledge since it does not exists
•  » » 6 years ago, # ^ |   0 Is number 121 prime?
 » 6 years ago, # |   +13 I think if you study Number Theory,you won't have any problems in these questions in future :)
 » 5 years ago, # |   0
•  » » 2 years ago, # ^ |   0 Thanks, nice article.