Блог пользователя shyam81295

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

Автор shyam81295, история, 9 лет назад, По-английски

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
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
← 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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

→ Ответить