время распечатки всех простых чисел под N

Question

int main() {
      int i, a[N];
      // initialize the array
      for(i = 2; i < N; i++) a[i] = 1;
      for(i = 2; i < N; i++)
         if(a[i])
              for(int j = i; j*i < N; j++) a[i*j] =0;
       // pirnt the primes less then N
       for(i = 2; i < N; i++)
           if(a[i]) cout << "  " << i;
       cout << endl;
}

Это было дано в книге алгоритмов, я читаю время выполнения вышеуказанной программы пропорционально N+N/2+N/3+N/5+N/7+N/11+...,

Пожалуйста, помогите мне понять, как автор придумал приведенное выше уравнение из программы. Спасибо! Venkata

Answer 1

Это метод "Сита Эратосфена" для поиска простых чисел.Для каждого простого теста if(a[i]) успешно выполняется и выполняется внутренний цикл.Рассмотрим, как заканчивается этот внутренний цикл на каждом шаге (помните, что условие j*i < N или, что эквивалентно, j < N/i):

• i = 2 -> j = 2, 3, 4,..., N / 2
• i = 3 -> j = 3, 4, 5, ..., N / 3
• i = 4 -> не простое число
• i = 5 -> j = 5, 6, 7, ..., N / 5
• ...

Суммирование общего количества операций (включая инициализацию массива/ извлечение простых чисел) дает время выполнения, упомянутое в книге.

Подробнее см. в этом вопросе , включая обсуждение того, как в терминах битовых операций это превращается в расширение O(n (log n) (log log n)) согласно статье Википедии .

Answer 2

Этот алгоритм называется Ситом Эратосфена.Это изображение объясняет все:

(из Википедии)

Answer 3

Внутренний цикл (внутри if(a[i])) выполняется только для простых i с. То есть для i, равного 2, 3, 5, 7, 11, ... А для одиночного i этот цикл имеет приблизительно N/i итераций Таким образом, мы имеем N/2 + N/3 + N/5 + N/7 + N/11 + ... итераций в целом.