Как работает данный алгоритм проверки числа на простоту и какой у него Big O??

Question

[Sudrap]

Код, как и сам алгоритм максимально простые и просто написаны, однако мне никак не удаётся понять момент в коде, который я ниже выделю жирным шрифтом. Что тут происходит? Я пытался чуть ли не вручную на бумаге пройти каждую итерации, например, с x = 7, однако на уже второй итерации при i =3 по логике условие цикла не соблюдается, так как 9 (i*i) не может быть меньше 8 (num+1). И зачем вообще присваивать a [j] значение 0? Также насчёт Big O непонятно. Предполагаю, что тут он выглядит, как O(logN), однако до конца не уверен, так как не понимаю работу вышеописанной части.
Прошу прощения, если мой вопрос вызвал у вас испанский стыд.

#include <iostream> 
#include <windows.h> 
 
using namespace std; 
 
const int x = 7; 
 
void number_type(int num) 
{ 
    int a[x]; 
    for (int i = 2; i < num + 1; i++) 
    { 
        if (a[i]) 
        { 
            <b>for (int j = i * i; j < num + 1; j += i) 
                a[j] = 0; </b>
        } 
    } 
    if (a[num]) 
        cout << num << " - простое число" << '\n'; 
    else 
        cout << num << " - составное число" << '\n'; 
} 
 
int main() 
{ 
    setlocale(LC_ALL, "Ru"); 
    number_type(x); 
    return 0; 
}

Comments

[Wataru]

Оберните код в тег code (кнопка </> в редакторе). Иначе вопрос удалят. И читать вопрос невозможно - форматирование у кода и его часть съедена. Вместо выделения жирным, поставьте в коде комментарий.

Answer 1

[Wataru]

Это вроде как решето Эратосфена (только с багами).

Этот цикл по идее помечает составными все числа, делящиеся на i (которое к этому моменту вроде как простое). Таким образом все составные числа должны быть помечены в массиве a.
Тут есть оптимизация: помечаются только те числа, для которых i - делитель не больше корня. Иначе бы цикл был не от i*i а от i. Эту оптимизацию можно делать, потому что у каждого числа обязательно есть простой делитель не больше корня, а значит и такой цикл пометит все составные числа.

Сложность тут O(n log(log n)) - Доказательство смотрите в википедии.

Answer 2

[jcmvbkbc]

Как работает данный алгоритм проверки числа на простоту

Данный алгоритм работает неправильно, первая ошибка состоит в том, что происходит обращение к неинициализированным элементам массива a.