1

我需要获得给定数字（ n ）的两个因子（ x, y ），以便：

  • x * y <= n
  • x * y 应尽可能接近 n
  • x 和 y 应尽可能靠近。

例子：

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

任何语言都可以，但最好是 php。

编辑——澄清

我想创建一个矩形，x 单位宽 * y 单位高，使其面积尽可能接近 n。x 和 y 必须是整数。如果 n 是素数，则 n - 1 的因数是可以接受的。

4

7 回答 7

5

你的规格不够准确。您说您想要因子，但在您的测试用例中，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) )
于 2009-12-07T14:39:41.457 回答
4

您需要确定您的三个规则的重要性。

可能性 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。但是，我怀疑这是什么无论哪个老师写这个作为家庭作业。

于 2009-12-07T14:52:04.210 回答
1

我的一个想法（比php更伪）

$root = sqrt($inputNumber);

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

if(($root - $x) > 0.5) $y++;
于 2009-12-07T14:51:09.927 回答
1 
$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
于 2009-12-07T14:57:27.967 回答
1

我将使用以下代码将所有因子写入数组。

#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

于 2012-09-18T10:07:20.240 回答
0

这是一个 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);
}
于 2009-12-07T14:59:22.860 回答
0

编写程序求任意数的因数

<?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>
于 2017-07-20T12:31:14.300 回答