@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 <drizzle...@gmail.com> 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 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.
