Алгоритмизация и программирование. Язык C++

Решето Эратосфена
Эратосфен Киренский
(Eratosthenes, Ερατοσθδνη)
(ок. 275-194 до н.э.)
Новая версия – решето Аткина. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Алгоритм:
начать с k = 2
«выколоть» все числа через k, начиная с 2·k
перейти к следующему «невыколотому» k
если k <= N , то перейти к шагу 2
напечатать все числа, оставшиеся «невыколотыми»
высокая скорость, количество операций
нужно хранить в памяти все числа от 1 до N
O((N·log N)·log log N )
2
3
k·k
k·k <= N

Решето Эратосфена
Задача. Вывести все простые числа от 2 до N.
Объявление переменных:
const int N = 100;
bool A[N+1];
int i, k;
Сначала все невычеркнуты:
for ( i = 2; i <= N; i++ )
A[i] = true;
выделяем на 1 элемент больше, чтобы начать с A[1]

Решето Эратосфена
Вычёркивание непростых:
k = 2;
while ( k*k <= N ) {
if ( A[k] ) {
i = k*k;
while ( i <= N )
{
A[i] = false;
i += k;
}
}
k ++;
}

Решето Эратосфена
Вывод результата:
for ( i = 2; i <= N; i++ ) if ( A[i] )
cout << i << " ";

Наибольший общий делитель (GCD)
gcd⁡(?,?): наибольшее целое число делящее нацело ? и ?
Используется очень часто в различных теоретических проблемах
Несколько фактов:
gcd(?,?)=gcd⁡(?,?−?)
gcd(?,0)=?
gcd⁡(?,?) наименьшее положительное число в {??+??⁡|⁡?,?∈?}

Алгоритм Евклида
Повторение gcd(?,?)=gcd⁡(?,?−?)
gcd(1989,867) =
gcd(1989−2×867,867) =
gcd(255,867) =
gcd(255,867−3×255) =
gcd(255,102) =
gcd(255−2×102,102) =
gcd(51,102) =
gcd(51,102−2×51) =
gcd(51,0) =51