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.

fibonacci

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