优化
1.枚举到sqrt(n)2.区间有质数直接输出最大质数3.a=1 直接输出1 4.边+边与最小值比较
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<cmath>
using namespace std;
#define N 1000010
double minz = N;
bool f[N];
void init()
{
int i,j;
for(i = ; i <= ; i++)
{
if(!f[i])
{
for(j = i+i ; j <= N- ; j+=i)
f[j] = ;
}
}
}
double find(int k)
{
int i;
int x = sqrt(k*1.0);
double sum=;
sum+=;
for(i = ; i <= x ; i++)
{
if(k%i==)
{
sum+=k/i+i;
}
if(sum/k>minz) break;
}
return sum/k;
}
int main()
{
int i,a,b;
init();
cin>>a>>b;
int ans=-;
if(a==)
{
printf("1\n");
return ;
}
for(i = a ; i <= b ; i++)
{
if(!f[i]) ans = i;
}
if(ans!=-)
{
printf("%d\n",ans);
return ;
}
for(i = a; i <= b ; i++)
{
double s = find(i);
if(s<minz)
{
ans = i;
minz = s;
}
}
printf("%d\n",ans);
return ;
}