优化
1.枚举到sqrt(n)2.区间有质数直接输出最大质数3.a=1 直接输出1 4.边+边与最小值比较
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<cmath> 7 using namespace std; 8 #define N 1000010 9 double minz = N; 10 bool f[N]; 11 void init() 12 { 13 int i,j; 14 for(i = 2 ; i <= 1000 ; i++) 15 { 16 if(!f[i]) 17 { 18 for(j = i+i ; j <= N-10 ; j+=i) 19 f[j] = 1; 20 } 21 } 22 } 23 double find(int k) 24 { 25 int i; 26 int x = sqrt(k*1.0); 27 double sum=0; 28 sum+=1; 29 for(i = 2 ; i <= x ; i++) 30 { 31 if(k%i==0) 32 { 33 sum+=k/i+i; 34 } 35 if(sum/k>minz) break; 36 } 37 return sum/k; 38 } 39 int main() 40 { 41 int i,a,b; 42 init(); 43 cin>>a>>b; 44 int ans=-1; 45 if(a==1) 46 { 47 printf("1 "); 48 return 0; 49 } 50 for(i = a ; i <= b ; i++) 51 { 52 if(!f[i]) ans = i; 53 } 54 if(ans!=-1) 55 { 56 printf("%d ",ans); 57 return 0; 58 } 59 for(i = a; i <= b ; i++) 60 { 61 double s = find(i); 62 if(s<minz) 63 { 64 ans = i; 65 minz = s; 66 } 67 } 68 printf("%d ",ans); 69 return 0; 70 }