求助以下代码的时间复杂度，在洛谷IDE上跑2^31-1用了438ms.

相关博文戳这儿

因为不太理解博文里的写法，所以就按递推式直接爆算了，出乎意料的不是很慢

#include<iostream> 
#include<cmath>
using namespace std;
const int MAXN=1e6+5;
int n,len;
int prime[MAXN];
bool isprime[MAXN];

inline int f(int k,int x){
	if( k==1 )
		return x-x/2;
	if( prime[k]*prime[k]<=x )
		return f(k-1,x)-f(k-1,x/prime[k])+(k-1);
	return f(k-1,x);
}

int main(){
	scanf("%d",&n);
	int lim=sqrt(n);
	for(int i=2;i<=lim;i++){
		if( !isprime[i] )
			prime[++len]=i;
		for(int j=1; i*prime[j]<=lim && j<=len; j++){
			isprime[i*prime[j]]=1;
			if( i%prime[j]==0 )
				break;
		}
	}
	printf("%d",n>3?f(len,n):n-1);
	return 0;
}