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.

http://e-maxx.ru/algo/prime_sieve_linear

Brief description in English.

I am sorry by mistake I downvoted you. Actually I liked your answer. I want to upvote but it's not getting changed :(

English version

I don't think that you will find many (or any) problems in which regular sieve is not enough.

http://www.spoj.com/problems/KPRIMES2/

Well, I guess I underestimated SPOJ's crazy optimization problems once again.

I clicked on your profile->submissions to see Haskell solutions. I feel cheated now.

It is well known that log(log(N))<=5 :)

One optimization in sieve

UPD.FixedIn the last "for" you can begin from j = i*i.

I can't, I must! Thanks :)

I think sieve runs faster than this code.

sieve — 4.05 s

your code — 6.21 s

so if you need to get all prime numbers <=n;do this

for(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..

Hi, I have doubt.. how much time it'll take u to completely destroy my algorithms knowledge ?

Then stop this method and go for sieve of Eratosthenes...

relax man,no matter how hard u try...

u cannot destory which does not exist,

r u good at algos then??????.....raing???

I mean say I know 0 about algorithms .. so u cannot destory my knowledge since it does not exists

Is number 121 prime?

I think if you study Number Theory,you won't have any problems in these questions in future :)

http://www.lightoj.com/article_show.php?article=1001

Thanks, nice article.