I think this works and the complexity is O(sqrt(n))
#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 = 1; j*j <= i; j++)
{
if (i % j == 0 && minDis > (i/j - j) )
{
minDis = i/j - j;
minDiv = j;
val = i;
}
}
}
cout<<val<<" "<<minDiv<<" "<<val/minDiv<<endl;
}
//system("pause");
return 0;
}
On Mar 22, 10:34 am, atul anand <[email protected]> wrote:
> @Rujin : mathematically point 2.2 seems straight forward but can we achieve
> value of x and y with an algo whose complexity wud be O(sqrt(E)) ??
>
>
>
>
>
>
>
> On Wed, Mar 21, 2012 at 2:37 PM, Rujin Cao <[email protected]> wrote:
> > One possible way is:
>
> > 1) Put the three candidate number together into an array [n, n + 1, n + 2]
> > 2) Iterate each element *E* in that array and test whether *E* is a prime
> > number
> > 2.1) If it is, there will be only one way to find the two numbers
> > product to be *E*, i.e. {x = 1, y = E} OR {x = E, y = 1}, so the result
> > is E - 1
> > 2.2) Otherwise, we should choose x and y that are closest to the
> > sqrt of *E*, which is quite straight forward.
> > E.g. 72 = 8 * 9 and 72 = 2 * 36 (2 < 8 and 36 > 9, so |9
> > - 8| < |36 - 2|)
>
> > So total time complexity is O(sqrt(E)).
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
