2
$\begingroup$

The goal is to find a generalized way to express a number as product of its factors, whose difference is close to zero.

For example,

n = 12;

12 = 3*4 (or) 2*6 (or) 12*1

The factors which are close to each other are 3 & 4.

Likewise, how do I find for a number 'N'?

I came across this question in a book, however I didn't find the solution anywhere.

$\endgroup$
5
  • $\begingroup$ Aiya, that impossible integer factorisation problem again! $\endgroup$ May 11, 2017 at 14:43
  • $\begingroup$ Are you asking this question about a number you have already factored into primes, or is factoring part of the problem? If the latter there's no known good quick way. Can you give us more context from "the book"? $\endgroup$ May 11, 2017 at 14:47
  • $\begingroup$ @EthanBolker: I think even if you know the prime factorization it is hard, feeling like subset sum. If you take logs you are looking for the collection of prime factors whose sum is closes to half the log of $N$. Suppose $N=2^{517}3^{133}5^{47}104729$, for example $\endgroup$ May 11, 2017 at 14:50
  • $\begingroup$ @RossMillikan Agreed. But if that's the problem it's at least better formulated. And you can post your comment as an answer. $\endgroup$ May 11, 2017 at 14:51
  • $\begingroup$ No, 'N' is relatively small. ( < 10^6 ). @EthanBolker, no you dont know the primes before hand. :/ I read this problem months ago in a library, I don't exactly remember the name of the book though. $\endgroup$
    – Raghav
    May 11, 2017 at 14:53

1 Answer 1

4
$\begingroup$

Start from $\lfloor\sqrt{N}\rfloor$ and check every integer before it ($\lfloor\sqrt{N}\rfloor-1,\lfloor\sqrt{N}\rfloor-2,\cdots$) until you get a factor of $N$. Thus if $a$ is the largest factor of $N$, $\leq\lfloor\sqrt{N}\rfloor$, then $N=a\times\frac{N}{a}$ is the desired factorization.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .