Please subscribe to the official Codeforces channel in Telegram via the link ×

Need of Efficient algorithm to generate prime numbers in O(N) time complexity

Revision en1, by shyam81295, 2015-08-17 19:33:52

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.

Tags prime numbers, o(n), algorithm


  Rev. Lang. By When Δ Comment
en1 English shyam81295 2015-08-17 19:33:52 576 Initial revision (published)