Решето Эратосфена



Дано число
Необходимо найти все простые числа меньше либо равные данному числу

Пусть дано число n. Запишем все натуральные числа от 2 до n. Будем по порядку рассматривать числа и вычёркивать все остальные числа, которые кратны рассматриваемому. В результате невычеркнутыми останутся только простые числа.

Асимптотика O(nlog(logn)).


Листинг С++

int sieve_of_eratosthenes (int n, int v[])
{
   int i, j;
   for (i = 0; i <= n; ++ i)
      v[i] = 1;
   v[0] = 0;
   v[1] = 0;
   for (i = 2; i <= n; ++ i)
      for (j = i + i; j <= n; j += i)
         v[j] = 0;
   int cnt = 0;
   for (i = 0; i <= n; ++ i)
      if (v[i])
         cnt += v[i];
   return cnt;
}

14:23
03.02.2010


По всем вопросам обращаться: rumterg@gmail.com