Функция Эйлера простыми словами
функция Эйлера, если в двух словах возвращает количество взаимно простых чисел в промежутке от [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.
Усе! Дякую за увагу! Обов'язково розберіть цей алгоритм самостійно на листочку.
напишіть які алгоритми ви хочете що б я розібрав у подальшому?
