我写了一个玄学优化的计算欧拉函数程序，如下：

#include<bits/stdc++.h>

using namespace std;
//Miller_Rabin
long long qpow(long long a,long long times,long long p)
{
	long long ans=1;
	while(times)
	{
		if(times&1)ans=(long long)ans*a%p;
		a=(long long)a*a%p;
		times>>=1;
	}
	return ans;
}

const int test_time=7;

const long long primes[]={2,325,9375,28178,450775,9780504,1795265022};

bool millerRabin(long long n) {
  if (n < 3 || n % 2 == 0) return n == 2;
  if (n % 3 == 0) return n == 3;
  long long u = n - 1, t = 0;
  while (u % 2 == 0) u /= 2, ++t;
  for (int i = 0; i < test_time; ++i) {
    int a = primes[i]%n;
    if(a==0||a==1||a==n-1)continue;
	long long v = qpow(a, u, n);
    if (v == 1) continue;
    int s;
    for (s = 0; s < t; ++s) {
      if (v == n - 1) break;
      v = (long long)v * v % n;
    }
    if (s == t) return 0;
  }
  return 1;
}

long long eular(long long n)//计算
{
	long long ans=n;
	//if(millerRabin(n))return n-1;
	for(long long i=2;i*i<=n;i++)
	{
		if(!(n%i))
		{
			ans=ans*(i-1)/i;
			while(!(n%i))n/=i;
			//if(millerRabin(n))break;
		}
	}
	if(n!=1)return ans*(n-1)/n;
	else return ans;
}

它看起来是 $O(\sqrt[3]{n})$ 的，但似乎在计算从 1 到 INT_MAX 的欧拉函数时复杂度小于上界。

所以，针对这个问题，有更精确的上界吗？