题意：给定一个整数 N （ 0 ≤ N ≤ 1e12 ），求 N 内有多少个数能写成 a²×b×c² 的形式（ a,b,c 均为素数）。

有没有算法不超过 O(n) 的，我只写了一个 O(n³) 的，爆TLE，求助

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+10;
long long n,sum=0;
bool kun(long long x){
	int a[maxn];
	for(int i=2;i<=x;i++){
		int k=0;
		while(x%i==0){
			k++;
			x/=i;
			if(x==1) break;
		}
		a[i]=k;
	}
	for(int i=1;i<=x;i++){
		for(int j=i+1;j<=x;j++){
			for(int p=j+1;p<=x;p++){
				if(a[i]==2&&a[j]==1&&a[p]==2) return true;
			}
		}
	}
	return false;
}
int main(){
    scanf("%lld",&n);
    for(long long i=300;i<=n;i++){
    	if(kun(i)) sum++;
	}
	cout<<sum;
    return 0;
}