3

Необходимо найти функцию Эйлера от входящего значения, моя программа не укладывается в 2 секунды, как ускорить?

#include <iostream>
#include <cmath>
using namespace std;
int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    long long n,res=1,k=0;
    cin >> n;

    for (int i=2;i*i<n+1;i++){
      while (n%i == 0){
          k++;
          n/=i;
      }
      if(k)
        res*=pow(i,k-1)*(i-1); 
    }
    if(n-1)
        res*=(n-1);
    cout << res;
    return 0;
}
1

1 ответ 1

2
  1. У вас в коде почему-то не обнуляется k
  2. Есть на много более удобная формула для программного подсчета функции Ейлера: введите сюда описание изображения

вот реализация:

long long res = n;
for (long long i=2; i*i<=n; ++i)
    if (n % i == 0) {
        while (n % i == 0)
            n /= i;
        result -= result / i;
    }
if (n > 1)
    result -= result / n;

код честно взят с емакса.

1
  • Время выполнения O(sqrt(n)), будет проходить за 2 секунды, если n <= 10^13
    – Wsl_F
    19 июл 2016 в 11:13

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.