Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)
share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.