It is necessary to find the Euler function from the incoming value, my program does not fit into 2 seconds, how to speed up?

#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 answer 1

  1. For some reason, your code does not reset k
  2. There is a much more convenient formula for programmatically calculating the Euler function: enter image description here

here is the implementation:

 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;

The code is honestly taken from emaks .

  • O (sqrt (n)) execution time, will pass in 2 seconds if n <= 10 ^ 13 - Wsl_F