Получить делители числа
Вопрос
Мне нужно получить два множителя ( 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.
Решение
Ваши характеристики были недостаточно точными.Вы заявили, что вам нужны факторы, но в вашем тестовом примере 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) )
Другие советы
Вам нужно решить, насколько важны ваши три правила.
Возможность 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.Однако я сомневаюсь, что учитель написал это в качестве домашнего задания.
$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
Идея от меня (скорее псевдо, чем php)
$root = sqrt($inputNumber);
$x = floor($root);
$y = floor($root);
if(($root - $x) > 0.5) $y++;
Я бы записал все факторы в массив, используя следующий код.
#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
Вот функция 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);
}
Написать программу для нахождения делителя любого числа.
<?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>