БлогNot. Считаем функцию Эйлера с помощью решета

Считаем функцию Эйлера с помощью решета

Известно, что функция Эйлера широко применяется как в математических исследованиях, так и в ряде смежных областей, например, в криптографии.

Попробуем написать её простую реализацию, пригодную для многократных вычислений.

Идея состоит в том, чтобы найти все простые числа до предела счёта, равного, например, 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 просмотров]


теги: c++ числа алгоритм математика

К этой статье пока нет комментариев, Ваш будет первым