but the worst case still remains O(sqrt(E)) --
Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad <http://gplus.to/amolsharma99> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/> On Fri, Mar 23, 2012 at 7:12 AM, Rujin Cao <drizzle...@gmail.com> wrote: > @atul: > Anurag's code has illustrated the idea of O(sqrt(E)) solution. > > One more thing to optimize is that we can safely break after finding the > first factor of E which is less than sqrt(E). > So the code could be changed to: > > #include<cmath>#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>using > namespace std; > #define INFY 1000000007 > int main() > { > int n, i, j; > int val, minDiv, minDis; > while(1) > { > cin >> n; > minDis = INFY; > for (i = n; i <= n+ > 2; i++) > { > *for (j = sqrt(i * 1.0); j > 0; j--)* > > { > if (i % j == 0 && minDis > (i/j - j) ) > { > minDis = i/j - j; > minDiv = j; > val = > i; > *break;* > > } > } > } > cout<<val<<" "<<minDiv<<" "<<val/minDiv<<endl; > } > //system("pause"); > return 0; > } > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
