Obter fatores de um número
Pergunta
Eu preciso dois fatores (x, y) de um determinado número (n) tal que:
- x * y <= n
- x * y deve ser tão próxima quanto possível n
- x e y devem ser tão próximos uns dos outros quanto possível.
Exemplos:
- n = 16 => x = 4, y = 4
- n = 17 => x = 4, y = 4
- n = 18 => x = 6, y = 3
- n = 20 => x = 5, y = 4
Qualquer linguagem vai fazer, mas de preferência php.
EDIT - ESCLARECIMENTO
Eu quero criar um retângulo, unidades x largura * y unidades de altura tal que a sua área é tão perto de n possível. x e y devem ser inteiros. Se n é um número primo, então factores de n - 1 são aceitáveis ??
.Solução
As suas especificações não eram bastante exata o suficiente. Você disse que você queria fatores, mas em seu caso de teste 4 não um fator de 17
O seguinte código pseudo trabalhos priorizando que um fator é exata ??em>
for i in range(ceiling(sqrt(n)), 1){
if ( n modulo i ) == 0 {
x = i
y = round(n/i)
}
}
Onde como uma declaração sqrt simples irá trabalhar para garantir que os números são tão próximas quanto possível, mas não garante que eles são fatores.
x = y = round( sqrt(n) )
Outras dicas
Você precisa decidir o quão importante as três regras.
for(i = floor(sqrt(n)) .. 1) {
if n % i ==0 {
x = i;
y = n/x;
break;
}
}
Possibilidade 2: Se estar próximos uns dos outros é mais importante do que você esperaria n = 18 => 4,4 em vez de 3,6, e este código iria funcionar. Este, porém, não é fatores.
x=floor(sqrt(n))
y=floor(n/x)
O problema como escrito é insolúvel, sem uma especificação mais clara.
Editar ------------
Agora, a especificação foi editado agora está definido, mas você precisa fazer Possibilidade 1, ver se o resultado é primo (1 é um dos valores) e, em seguida, se for repita fazendo Possibilidade 2. No entanto, duvido isto é o que qualquer que seja o professor escreveu isso como lição de casa destina-se.
$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
Uma idéia de mim (mais pseudo então php)
$root = sqrt($inputNumber);
$x = floor($root);
$y = floor($root);
if(($root - $x) > 0.5) $y++;
Eu teria todos os fatores escritos para uma matriz usando o seguinte código.
#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
Então eu percorrer a matriz para verificar quais realmente pode ser usado. Para saber mais sobre este algoritmo, veja http : //pyfon.blogspot.com.au/2012/09/list-factors-of-number-in-python.html
Aqui é uma função PHP que priorizar os dois 'fatores' sendo perto uns dos outros por ter fatores exatos:
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);
}
Escreva um programa para encontrar fator de qualquer número
<?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>