Obtenez des facteurs d'un nombre

Question

je dois obtenir deux facteurs (x, y) d'un nombre donné (n) tel que:

• x * y < = n
• x * y devrait être aussi proche de n possible
• x et y doivent être aussi proches l'un de l'autre que possible.

Exemples:

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

Toute langue fera, mais de préférence php.

EDIT - CLARIFICATION

Je veux créer un rectangle, unités x largeur * unités y hauteur telle que sa région est aussi proche que possible n. x et y doivent être des entiers. Si n est un nombre premier, alors les facteurs de n - 1 sont acceptables.

Answer 1

Vos spécifications n'étaient pas assez précises. Vous avez dit que vous vouliez facteurs, mais dans votre cas test 4 n'est pas un facteur de 17

Le pseudo-code suivant fonctionne priorise que l'un des facteurs est exact

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

Où comme un simple sqrt La déclaration permettra de s'assurer que les chiffres sont aussi proches que possible, mais ne garantit pas qu'ils sont des facteurs.

x = y = round(sqrt(n)) 

Answer 2

Une idée de moi (plus pseudo puis php)

$root = sqrt($inputNumber); 

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

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

Answer 3

Vous devez décider à quel point vos trois règles.

Possibilité 1: Si x * y étant aussi proche de n que possible, alors n = 17 => 1,17 pas 4,4. Dans ce cas, vous voulez factorisation et il y a beaucoup de façons de le faire, mais le code comme ceci est simple:

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

Possibilité 2: Si la proximité de l'autre est plus important que vous attendez n = 18 => 4,4 plutôt que 3,6, et ce code fonctionnerait. Ce n'est cependant pas des facteurs.

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

Le problème tel qu'il est écrit est insoluble sans spécification plus claire.

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

Maintenant, la spécification a été modifié, il est maintenant défini, mais vous devez faire Possibilité 1, voir si le résultat est premier (1 est l'une des valeurs) et ensuite si c'est répéter la possibilité 2. Cependant, je doute que ce soit ce que n'importe quel enseignant a écrit cela comme devoir.

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

Voici une fonction PHP qui accordent la priorité aux deux « facteurs » étant proches les uns des autres sur ayant des facteurs précis:

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 6

j'aurais tous les facteurs écrits à un tableau en utilisant les éléments suivants code. Ensuite, je ferais une boucle dans le tableau pour vérifier lesquels peuvent réellement être utilisés. Pour en savoir plus sur cet algorithme, consultez http://pyfon.blogspot.com.au/2012/09/list-factors-of-number-in-python.html

Answer 7

Ecrire un programme pour trouver le facteur d'un nombre

<?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>