shyam81295's blog

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

By shyam81295, history, 9 years ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

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

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

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it -23 Vote: I do not like it

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

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

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

→ Reply