Obtener los factores de un número
Pregunta
Necesito conseguir dos factores ( x, y ) de un número dado ( n ) tal que:
- x * y <= n
- x * y debe ser lo más parecido a n como sea posible
- x e y deben estar tan cerca el uno del otro como sea posible.
Ejemplos:
- n = 16 => x = 4, y = 4
- n = 17 => x = 4, y = 4
- n = 18 => x = 6, y = 3
- n = 20 => x = 5, y = 4
Cualquier idioma va a hacer, pero preferiblemente php.
EDITAR -- ACLARACIÓN
Quiero crear un rectángulo, x unidades de ancho * y unidades de altura tal que su área está tan cerca de la n como sea posible.x e y deben ser números enteros.Si n es un número primo, entonces los factores de n - 1 son aceptables.
Solución
Sus especificaciones no muy exacta suficiente.Usted dijo que usted quería factores, sin embargo, en el caso de prueba 4 no es un factor de 17
El siguiente pseudo código funciona la priorización de que uno de los factores es exacto
for i in range(ceiling(sqrt(n)), 1){
if ( n modulo i ) == 0 {
x = i
y = round(n/i)
}
}
Donde como un simple sqrt instrucción de trabajo para garantizar que los números estén tan cerca como sea posible, pero no es garantía de que se trata de factores.
x = y = round( sqrt(n) )
Otros consejos
Es necesario decidir la importancia de sus tres reglas.
Posibilidad 1: Si x * y estar tan cerca de n como sea posible es cierto, entonces n = 17 => 1,17 no 4,4. En este caso desea factorización y hay un montón de maneras de hacerlo, pero el código como esto es simple:
for(i = floor(sqrt(n)) .. 1) {
if n % i ==0 {
x = i;
y = n/x;
break;
}
}
Posibilidad 2: Si estar cerca uno del otro es más importante lo que espera n = 18 => 4,4 en lugar de 3,6, y este código funcionaría. Sin embargo, esto no es factores.
x=floor(sqrt(n))
y=floor(n/x)
El problema como escrito es imposible de resolver sin una especificación más clara.
Editar ------------
Ahora la especificación ha sido editado ahora está definido, pero hay que hacer Posibilidad 1, ver si el resultado es primo (1 es uno de los valores) y luego si se repita haciendo Posibilidad 2. Sin embargo, dudo esto es lo que lo que el maestro escribió esto como tarea prevista.
$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
Una idea de mí (más de pseudo, entonces PHP)
$root = sqrt($inputNumber);
$x = floor($root);
$y = floor($root);
if(($root - $x) > 0.5) $y++;
Tendría que todos los factores escritas a una matriz mediante el siguiente 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
Entonces me bucle a través de la matriz para comprobar cuáles en realidad puede ser utilizado. Para más información sobre este algoritmo, echa un vistazo a http : //pyfon.blogspot.com.au/2012/09/list-factors-of-number-in-python.html
Aquí es una función PHP que priorizan los dos 'factores' estar cerca el uno al otro por tener factores exactas:
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);
}
Escribir un programa para encontrar el factor de cualquier 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>