有以下代码：

#include<bits/stdc++.h>
using namespace std;
int pr[10000005],tot=0;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	long long cnt=0; 
	for(int i=2;i<=n;i++){
		bool flag=1;
		for(int j=1;j<=tot;j++){
			cnt++;
			if(i%pr[j]==0){
				flag=0;
				break;
			}
			if(1ll*pr[j]*pr[j]>i) break;
		}
		if(flag) pr[++tot]=i;
	}
	cout<<cnt<<'\n';
}

显然该代码会在数组 $pr$ 中存入 $1\sim n$ 的所有素数。由于 $1\sim n$ 中的素数个数约有 $\mathcal{O}(\frac{n}{\ln n})$ 个，故其复杂度上界为 $\mathcal{O}(n\times \frac{\sqrt{n}}{\ln \sqrt{n}})=\mathcal{O}(\frac{n\sqrt{n}}{\ln n})$，当强制令 $i$ 为素数时的时间复杂度为 $\mathcal{O}(\frac{n}{\ln n}\times \frac{\sqrt{n}}{\ln \sqrt{n}})=\mathcal{O}(\frac{n\sqrt{n}}{\ln^2 n})$。但是当 $n=10^7$ 时它的运行次数（即代码中的 $cnt$）为 286809516，与上述复杂度上界（约为 $1.9\times 10^9$）并不接近，反而与强制令 $i$ 为素数时的时间复杂度（约为$1.2\times 10^8$） 十分接近，所以求问上述代码的时间复杂度。