Получить делители числа

Question

Мне нужно получить два множителя ( x, y ) заданного числа ( n ) так, чтобы:

• х * у <= п
• x * y должно быть как можно ближе к n
• x и y должны быть как можно ближе друг к другу.

Примеры:

• п = 16 => х = 4, у = 4
• п = 17 => х = 4, у = 4
• п = 18 => х = 6, у = 3
• п = 20 => х = 5, у = 4

Подойдет любой язык, но желательно PHP.

РЕДАКТИРОВАТЬ - РАЗЪЯСНЕНИЕ

Я хочу создать прямоугольник шириной x единиц x высотой y, чтобы его площадь была как можно ближе к n.x и y должны быть целыми числами.Если n — простое число, то допустимы коэффициенты n — 1.

Answer 1

Ваши характеристики были недостаточно точными.Вы заявили, что вам нужны факторы, но в вашем тестовом примере 4 не является коэффициент 17

Следующий псевдокод работает с приоритетом одного фактора. точный

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

Простой оператор sqrt будет работать для обеспечения максимально близкого расположения чисел друг к другу, но не гарантирует, что они являются факторами.

x = y = round( sqrt(n) )

Answer 2

Вам нужно решить, насколько важны ваши три правила.

Возможность 1: Если x * y является максимально близким к n, то n=17 => 1,17, а не 4,4.В этом случае вам нужна факторизация, и есть много способов сделать это, но такой код прост:

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

Возможность 2: Если близость друг к другу важнее, вы ожидаете, что n=18=>4,4, а не 3,6, и этот код будет работать.Однако это не является фактором.

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

Проблема в том виде, в котором она написана, неразрешима без более четкой спецификации.

РЕДАКТИРОВАТЬ ------------

Теперь спецификация отредактирована, она теперь определена, но вам нужно выполнить Возможность 1, посмотреть, является ли результат простым (1 — одно из значений), а затем, если он повторяется, повторить Возможность 2.Однако я сомневаюсь, что учитель написал это в качестве домашнего задания.

Answer 3

$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 4

Идея от меня (скорее псевдо, чем php)

$root = sqrt($inputNumber);

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

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

Answer 5

Я бы записал все факторы в массив, используя следующий код.

#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

Затем я просматривал массив, чтобы проверить, какие из них действительно можно использовать.Подробнее об этом алгоритме см. http://pyfon.blogspot.com.au/2012/09/list-factors-of-number-in-python.html

Answer 6

Вот функция PHP, которая отдает приоритет двум «факторам», близким друг к другу, а не точным факторам:

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 7

Написать программу для нахождения делителя любого числа.

<?php
if(isset($_POST['sub']))
 {     $j=0;
   $factor=array(); 
   $num=$_POST['nm1'];
   for($i=1;$i<=$num;$i++)  
       {
          if($num%$i==0)
            { 
             $j++;
             $factor[$j]=$i;
            }
       }
}
 ?>

 <table>
 <form name="frm" method="post" action="">
 <tr> <td>Number:</td> <td><input type="text" name="nm1" /></td> </tr>
 <tr><td></td><td><input type="submit" name="sub" /></td>
 <td><center><span>  
  <?php   
    if(isset($_POST['sub']))  
    { 
       echo "Factors are :";for($i=1;$i<=count($factor);$i++) 
       {          echo $factor[$i].",";

        }
     }       
  ?>   
   </span></center></td></tr>
 </form>
 </table>