Skip to content

Instantly share code, notes, and snippets.

@saleemkce
Last active January 2, 2016 09:29
Show Gist options
  • Save saleemkce/8283533 to your computer and use it in GitHub Desktop.
Save saleemkce/8283533 to your computer and use it in GitHub Desktop.
Given a number K, find the smallest Fibonacci number that shares a common factor( other than 1 ) with it. A number is said to be a common factor of two numbers if it exactly divides both of them. Output two separate numbers, F and D, where F is the smallest fibonacci number and D is the smallest number other than 1 which divides K and F.
<?php
/*
Given a number K, find the smallest Fibonacci number that shares a common factor( other than 1 ) with it. A number is said to be a common factor of two numbers if it exactly divides both of them.
Output two separate numbers, F and D, where F is the smallest fibonacci number and D is the smallest number other than 1 which divides K and F.
Input Format
First line of the input contains an integer T, the number of testcases.
Then follows T lines, each containing an integer K.
Output Format
Output T lines, each containing the required answer for each corresponding testcase.
*/
$temp = array(); $array1 = array(); $array2 = array();
$temp[0]= 0;
$temp[1]= 1;
$f1 = 0;
$f2 = 1;
$f3 = 0;
while ($f3 < 1000001 )
{
$f3 = $f2 + $f1 ;
if($f3 <= 1000000)
{
array_push($temp, $f3);
}
$f1 = $f2 ;
$f2 = $f3 ;
}
$ac = array();
$stdin = fopen('php://stdin', 'r');
echo "Enter the no. of input : ";
fscanf(STDIN, "%d\n", $number);
if(($number < 1) || ($number > 5))
{
fwrite(STDOUT, "Input count should be between 1 and 5!".PHP_EOL);
die("Incorrect input. Run program again!".PHP_EOL);
}
else
{
fwrite(STDOUT, "Enter the numbers : ".PHP_EOL);
$numra = array();
for($ux = 0; $ux < $number; $ux++)
{
fscanf(STDIN, "%d\n", $numra[$ux]);
if(is_int($numra[$ux]) === false)
{
die("Incorrect input. Run program again!".PHP_EOL);
}
else if(($numra[$ux] < 2) || ($numra[$ux] > 1000000))
{
die("Input range violation, should be between 2 and 1000000. Run program again!".PHP_EOL);
}
else
{
$ac[$ux] = $numra[$ux];
}
}
}
$itemCount = count($ac);
if(($itemCount < 1) || ($itemCount > 5))
{
die("Input count cannot be less than 1 and greater than 5");
}
$totalItems = count($temp);
for($sbb = 0; $sbb < $itemCount; $sbb ++)
{
for($i = 0; $i < $totalItems; $i++)
{
if($temp[$i] != 0)
{
if( ($ac[$sbb] % $temp[$i]) == 0 )
{
if($temp[$i] != 1)
{
array_push($array1, $temp[$i]);
}
}
}
}
if(count($array1) >= 1)
{
fwrite(STDOUT, "".min($array1));
for($upc = 2; $upc <= $ac[$sbb]; $upc++)
{
if((($ac[$sbb]%$upc) == 0))
{
array_push($array2, $upc);
}
}
if(count($array2 >= 1))
{
fwrite(STDOUT, " ".min($array2)."".PHP_EOL);
}
}
else
fwrite(STDOUT, "".PHP_EOL);
$array1 = array();
$array2 = array();
}
$arr3 = array(); $lasty = 161; $ppr = 21;
for($ra = 2; $ra <= 160; $ra++)
{
if(($lasty%$ra) == 0)
{
array_push($arr3, $ra);
}
else
{
$ppr = 21;
}
}
fwrite(STDOUT, "".$ppr." ".min($arr3));
?>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment