Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

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

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

Пусть дано число 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