从n开始也可以,或者像我一样从sqrt(n)开始也可以,就是要做些处理

上代码!

#include<bits/stdc++.h>
using namespace std;
int n,ans;
bool zs(int n){//用普通的质数判定也可以
    float n_sqrt;
    if(n==1) return false;
    if(n==2||n==3) return true;
    if(n%6!=1&&n%6!=5) return false;
    n_sqrt=floor(sqrt((float)n));
    for(int i=5;i<=n_sqrt;i+=6)
        if(n%(i)==0 | n%(i+2)==0) return false;
    return true;
}
int main(){
    cin>>n;
    if(n%2==0){
        cout<<n/2;
        return 0;
    }
    ans=sqrt(n);
    if(n%ans==0){
        cout<<ans;
        return 0;
    }
    if(ans%2==0) ans++;
    while(ans+=2) if(zs(ans)&&n%ans==0) break;
    cout<<ans;
    return 0;
}