直接暴力就行

#include<bits/stdc++.h>
using namespace std;
bool prime(int a){//判断是否为质数
	bool z=true;
	for(long long n=2;n<=sqrt(n);n++){//注意：判断到sqrt(n)就足够了
		if(a%n==0){
			z=false;
		}
	}
	return z;
}
int main(){
	long long n,k=2,j=1;
	cin>>n;
	while(j){
		if(n%k==0){
			if(prime(n/k)){//注意：由于是从最小数开始的，所以应该判断和输出的应是(n/k)
				j=0;
				cout<<n/k;
			}
		}
		else{
			k++;
		}
	}
}

最大时间复杂度O(n * sqrt(n))