Get factors of a number

Question

I need to get two factors ( x, y ) of a given number ( n ) such that:

• x * y <= n
• x * y should be as close to n as possible
• x and y should be as close to each other as possible.

Examples:

• n = 16 => x = 4, y = 4
• n = 17 => x = 4, y = 4
• n = 18 => x = 6, y = 3
• n = 20 => x = 5, y = 4

Any language will do but preferably php.

EDIT -- CLARIFICATION

I want to create a rectangle, x units wide * y units tall such that its area is as close to n as possible. x and y must be integers. If n is a prime number then factors of n - 1 are acceptable.

Answer 1

Here is a PHP function that prioritize the two 'factors' being close to each other over having exact factors:

function weird_factors($ori) {
    $sq = intval(sqrt($ori));
    $start = $sq - 10;
    $end = $sq + 10;
    $n = 0;
    for ($s = $start; $s <= $end; $s++) {
        for ($t = $start; $t <= $end; $t++) {
            $st = $s * $t;
            if ($st <= $ori and $st > $n) {
                $n = $st;
                $ns = $s;
                $nt = $t;
            }
        }
    }
    return array($ns, $nt);
}

Answer 2

An idea from me (more pseudo then php)

$root = sqrt($inputNumber);

$x = floor($root);
$y = floor($root);

if(($root - $x) > 0.5) $y++;

Answer 3

I'd have all the factors written to an array using the following code.

#Application lists all factors/divisors for a number.
targetNumber=input('What number do you want the factors for?\n> ')
factors=[]
for i in range(1,targetNumber):
    if targetNumber%i==0:
        factors.append(i)
    elif targetNumber/i==1:
        factors.append(targetNumber)
        break
print factors

Then I'd loop through the array to check which ones can actually be used. For more on this algorithm, check out http://pyfon.blogspot.com.au/2012/09/list-factors-of-number-in-python.html

Answer 4

$num = ...; // some number

if (is_prime($num)) // implement the is_prime() function yourself
    --$num; // Subtract to get an even number, which is not a prime

$candidates = array();  // Numbers that may fit.

$top_search = $num / 2; // Limits the useless search for candidates

for($i=1; $i < $top_search; ++$i)
{
    if ($num % $i == 0)
        $candidates[$i] = $num / $i;
}

// Now, check the array in the middle 

Answer 5

Your specifications weren't quite exact enough. You stated that you wanted factors, yet in your test case 4 is not a factor of 17

The following pseudo code works prioritizing that one factor is exact

for i in range(ceiling(sqrt(n)), 1){
    if ( n modulo i ) == 0 {
          x = i
          y = round(n/i)
    }
}

Where as a simple sqrt statement will work for ensuring that the numbers are as close together as possible, but doesn't guarantee that they are factors.

x = y = round( sqrt(n) )

Answer 6

You need to decide how important your three rules are.

Possibility 1: If x * y being as close to n as possible is true then n=17 => 1,17 not 4,4. In this case you want factorisation and there are lots of ways to do it, but code like this is simple:

for(i = floor(sqrt(n)) .. 1) {
  if n % i ==0 {
     x = i;
     y = n/x;
     break;
  }
}

Possibility 2: If being close to each other is more important you'd expect n=18=>4,4 rather than 3,6, and this code would work. This however is not factors.

x=floor(sqrt(n))
y=floor(n/x)

The problem as written is unsolvable without a clearer specification.

EDIT ------------

Now the spec has been edited it is now defined, but you need to do Possibility 1, see if the result is prime (1 is one of the values) and then if it is repeat doing Possibility 2. However, I doubt this is what whichever teacher wrote this as homework intended.