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.
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. Fixed
In 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..
Is number 121 prime?
I think if you study Number Theory,you won't have any problems in these questions in future :)