Считаем функцию Эйлера с помощью решета
Известно, что функция Эйлера широко применяется как в математических исследованиях, так и в ряде смежных областей, например, в криптографии.
Попробуем написать её простую реализацию, пригодную для многократных вычислений.
Идея состоит в том, чтобы найти все простые числа до предела счёта, равного, например, 105 для наших скромных персоналок, используя решето Эратосфена и занести их в таблицу p.
Чтобы вычислить Φ(n), будем перебирать все простые числа, меньшие либо равные квадратному корню из n.
Если n делится на очередное число таблицы p[i] без остатка, удалим числа, кратные p[i] из результата, изначально равного n (удаляемые числа не будут иметь НОД, равный 1 со значением n).
Программка, показанная ниже, проверялась в консоли Visual Studio 2019.
#include <iostream> #include <vector> #include <cstring> using namespace std; const int MAX = 100001; //верхний предел обрабатываемых чисел vector <long long> p; //таблица void sieve() { //решето long long isPrime[MAX + 1]; memset (isPrime, 0, MAX + 1); //заполнить сначала нулями for (long long i = 2; i <= MAX; i++) { if (isPrime[i] == 0) { p.push_back(i); for (long long j = 2; i * j <= MAX; j++) isPrime[i * j] = 1; } } } long long phi(long long n) { long long res = n; for (long long i = 0; p[i] * p[i] <= n; i++) { // цикл выполнится sqrt(n / ln(n)) раз if (n % p[i] == 0) { res -= (res / p[i]); while (n % p[i] == 0) n /= p[i]; } } if (n > 1) res -= (res / n); return res; } int main() { sieve(); //нашли и сохранили решето cout << phi(50) << endl; //теперь считаем функцию cout << phi(100) << endl; cout << phi(500) << endl; cout << phi(1000) << endl; cout << phi(5000) << endl; cout << phi(10000) << endl; cout << phi(50000) << endl; cout << phi(100000) << endl; return 0; }
Полагаю, в этом онлайн-калькуляторе применены те же идеи.
21.12.2020, 16:12 [1055 просмотров]