Функция Эйлера простыми словами⁠⁠

функция Эйлера, если в двух словах возвращает количество взаимно простых чисел в промежутке от [1; n]. В программировании обозначается как phi(n). Несколько основных правил. Обозначим число за n

1) если n простое, то кол-во взаимно простых чисел от 1 будет равно на один меньше чем само число. Логично БЛЯТЬ!

2) Если n = c**k, то phi(n) = c**k - c**k-1; Доказывать это ясное дело это я не буду, так надо верь мне.

ну шо, давайте приступим непосредственно к написанию самого алгоритма.

int phi (int n) {

int result = n;  // запоминаем наше число, так надо верь мне.

for (int i=2; i*i<=n; ++i)  //ясен пень начинаем с двойки, ибо остаток при делении на 1 всегда 0  if (n % i == 0) {  // нахуй нам это надо

while (n % i == 0)  // если делится на i, то ищем другой множитель

n /= i;

result -= result / i; 

}

if (n > 1)

result -= result / n;

return result;

} 

Рассмотрим на простом примере. Возьмём число 18. Первый шаг, делится на 2, делится, заебись, делим наш n на 2 до посинения, n = 9, вычетаем получаем 9. круто, а то! Далее переходим к следующей итерации цикла, i = 3, i*i <= 9, верно, заебись. Дальше делим до того, n теперь 1, result = 6, но теперь, условие цикла не выполняется и мы из него выходим, но так же n !> 1 и мы просто возвращаем 6.

Всё! Спасибо за внимание! Обязательно разберите этот алгоритм самостоятельно на листочке.

напишите какие алгоритмы вы хотите что бы я разобрал в последующем? 

Укр.Версия

функція Ейлера, якщо в двох словах повертає кількість взаємно простих чисел в проміжку від [1; n]. У програмуванні позначається як phi (n). Кілька основних правил. Позначимо число за n

1) якщо n просте, то кількість взаємно простих чисел від 1 дорівнюватиме на один менше ніж саме число. Логічно блять!

2) Якщо n = c ** k, то phi (n) = c ** k - c ** k-1; Доводити це ясна річ це я не буду, так треба вір мені.

ну шо, давайте приступимо безпосередньо до написання самого алгоритму.

int phi (int n) {

int result = n; // запам'ятовуємо наше число, так треба вір мені.

for (int i = 2; i * i <= n; ++ i) // ясний пень починаємо з двійки, бо залишок при діленні на 1 завжди 0 if (n% i == 0) {// нахуй нам це треба

while (n% i == 0) // якщо ділиться на i, то шукаємо інший множник

n / = i;

result - = result / i;

}

if (n> 1)

result - = result / n;

return result;

Розглянемо на простому прикладі. Візьмемо число 18. Перший крок, ділиться на 2, ділиться, заебись, ділимо наш n на 2 до посиніння, n = 9, вичетаем отримуємо 9. круто, а то! Далі переходимо до наступної ітерації циклу, i = 3, i * i <= 9, вірно, заебись. Далі ділимо до того, n тепер 1, result = 6, але тепер, умова циклу не виконується і ми з неї виходимо, але так само n!> 1 і ми просто повертаємо 6.

Усе! Дякую за увагу! Обов'язково розберіть цей алгоритм самостійно на листочку.

напишіть які алгоритми ви хочете що б я розібрав у подальшому?