# Transform a positive integer to find its next greatest factor

Suppose I am trying to find factors of a particular positive integer num. Suppose I also have a function findGreatestFactor(num) that finds the greatest factor of a positive integer.

Is there a way to transform my integer num such that it would still have all of the same factors as the original num but findGreatestFactor(num) would find the next greatest factor of the original num?

Example:

let num = 100

findGreatestFactor(num) gives you 50 (the greatest factor of 100)

let num2 = some transformation of num

findGreatestFactor(num2) gives you 25 (the second greatest factor of 100)

let num3 = same transformation of num2

findGreatestFactor(num3) gives you 20 (the third greatest factor of 100)

-

If you consider the prime factorization $N = p_1 ^{q_1} \times p_2 ^{q_2} \times \ldots \times {p_n}^q_n$, where the $p_i$ are arranged in increasing order, then the smallest proper factor is $p_1$, and the next smallest factor is either $p_1 ^2$ or $p_2$.

Hence. Let $FGF$ be your findgrestestfactor. $Num/FGF(Num)$ will give you $p_1$. $Take FGF(Num)$ and divide out by $p_1$ repeatedly until we no longer get an integer. Say that the last integer is $N_1$. Then taking $\frac {N_1} {FGF(N_1)}$ will give you $p_2$. If $p_1^2 \not \mid N$, then $p_2$ is the second smallest factor. Otherwise, compare $p_1 ^2$ and $p_2$. Whichever is smaller, then $N/x$, will give you the second smallest factor.

-
This seems to be spot on for what OP wants. –  Ross Millikan Jan 2 '13 at 4:02
This shows that it is indeed possible to get the second largest factor from the FGF function, but it's not quite as straight forward as the OP wnated it. –  Hans Engler Jan 2 '13 at 4:24
this looks to be what I need. I will try it out when I get home later and accept if I get it working. Thank you. –  jbabey Jan 2 '13 at 13:21
@jbabey Note: Slight change to account for case where $p_1^2 \not \mid N$, doesn't really affect anything. –  Calvin Lin Jan 2 '13 at 13:37
@CalvinLin what if the factors i'm looking for are not always prime? –  jbabey Jan 2 '13 at 22:07

In your example, num2 would have 25 as greatest factor and 20 as second greatest factor. Then num2 must be a multiple of 100, and the greatest factor of num2 would be at least 50.

So this is impossible.

-