数値の約数を取得する

StackOverflow https://stackoverflow.com/questions/1860339

  •  13-09-2019
  •  | 
  •  

質問

次のように、指定された数値 ( n ) の 2 つの因数 ( 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 では ではありません 17 の係数

次の疑似コードは、1 つの要素を優先して動作します。 ちょうど

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

他のヒント

3 つのルールがどの程度重要かを判断する必要があります。

可能性 1: x * y が可能な限り n に近いことが true の場合、n=17 => 1,17 ではなく 4,4 になります。この場合、因数分解が必要であり、それを行う方法はたくさんありますが、次のようなコードは簡単です。

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

可能性 2: 互いに近いことがより重要な場合は、3,6 ではなく n=18=>4,4 が予想され、このコードは機能します。ただし、これは要因ではありません。

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

書かれている問題は、より明確な仕様がなければ解決できません。

編集 ------------

仕様が編集され、定義されましたが、可能性 1 を実行して、結果が素数 (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

以下は、正確な因子を持つことよりも、互いに近い 2 つの「因子」を優先する 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>
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top