一

$O(n)$

AC9,TLE25

#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n,s,cnt=0,ans=0;
	cin>>n;
	for(long long i=1;i*i<=n;i++){
		s=i*i;
		for(long long j=1;j*j<s;j++){
			if(s%j==0){
				cnt++;
			}
		}
		if(cnt==4){
			ans++;
		}
		cnt=0;
	}
	cout<<ans<<endl;
	return 0;
}

因为9是奇数，所以完全平方数才可能是答案，暴力枚举完全平方数

二:

AC6,WA3,RE25(为什么会RE)

$O(\sqrt{n}*\sqrt(\sqrt(n)))$

#include<bits/stdc++.h>
using namespace std;
long long d[6];
int main(){
	long long n,s,ans=0,fl=0;
	cin>>n;
	for(long long i=1;i*i<=n;i++){
		for(long long j=1;j<=4;j++){
			d[i]=0;
		}
		fl=0;
		d[1]=1;
		d[4]=n;
		for(long long j=2;j*j<=i;j++){
			if(i%j==0 and fl==1 and j!=i/j){
				fl=2;
			}
			else if(i%j==0 and j!=i/j){
				fl=1;
				d[2]=j;
				d[3]=i/j;
			}
		}
		if(d[2]*d[3]*d[2]*d[3]==i*i and fl==1 and d[2]*d[2]!=d[3]){
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

10=1,2,5,10;

100有（1，100），（2，50），（5，20）和（22，55）=（4，25）以及10

d[1]=1,d[4]=n,d[2],d[3]分别为中间两数