title: Amazon InterviewStreet Fibonacci Factor - PHP
body: <p>I am not able to solve the Amazon Interviewstreet challenge for fibonacci factor in php.
  <a href="https://amazon.interviewstreet.com/challenges/dashboard/#problems" rel="nofollow">https://amazon.interviewstreet.com/challenges/dashboard/#problems</a></p>
  
  <p>Fibonacci values upto <strong>10^18</strong></p>
  
  <p>large int values seem to be the problem and bcmath is not helping...</p>
  
  <p>My Code -</p>
  
  <pre><code>&lt;?php
  function s($k)
  {
  $x=$y=1;
      while($y&lt;=$k)
      {
      $z=$x+$y;
      $x=$y;
      $y=$z;
          if($y%2==0&amp;&amp;$k%2==0)
              {
                  fprintf(fopen("php://stdout", "w"), "%d ", 2);
                  fprintf(fopen("php://stdout", "w"), "%d\n", 2);
                  return;
              }
      for($i=3;$i&lt;=$y;$i+=2)
              if($y%$i==0&amp;&amp;$k%$i==0)
              {
                  fprintf(fopen("php://stdout", "w"), "%d ", $y);
                  fprintf(fopen("php://stdout", "w"), "%d\n", $i);
                  return;
              }
      }
      while($y%$k!=0)
      {
      $z=$x+$y;
      $x=$y;
      $y=$z;
      }
      fprintf(fopen("php://stdout", "w"), "%d ", $y);
      fprintf(fopen("php://stdout", "w"), "%d\n", $k);   
  }
  fscanf(STDIN, "%d\n", $t);
  while($t--)
  {
      fscanf(STDIN, "%d\n", $k);
      s($k);
  }
  ?&gt;
  </code></pre>