Hi all,
I'm new here and I'm trying my first 'challenge' with this problem, my main language is PHP so I tried this language first.
The problem is that the input reading is super slow even in my PC, but then the algorithm is fairly fast (once past the input phase), but the judge give me a time exceeded, probably because of the input phase.
Any change to speed up the reading of input??
My code is the following:
$n = intval(fgets( STDIN ));
$fifo = array();
$max = 0;
while($n>0){
$in = fgets( STDIN );
array_unshift($fifo,$in);
$bin = explode(" ",$in);
$m = intval($bin[1]);
if($m>$max) $max = $m;
$n--;
}
//$bt = microtime(true);
$pr = primes($max);
sort($pr);
//$at = microtime(true);
//$tt = $at-$bt;
while($op = array_pop($fifo)){
$bounds = explode(" ",$op);
$infbound = intval($bounds[0]);
$supbound = intval($bounds[1]);
foreach($pr as $p)
if($p>=$infbound && $p<=$supbound)
print $p."\n";
print "\n";
}
//print "Generated primes from 2 to $max in $tt seconds\n";
function primes($lim){
$sqrtlim = sqrt($lim);
$pp = 2;
$ss = array();
$ss[] = $pp;
$ep = array();
$ep[] = $pp;
$pp++;
$rss = array();
$rss[] = $ss[0];
$tp = array();
$tp[] = $pp;
$i = 0;
$rss[] = $rss[$i]*$tp[0];
$xp = array();
$pp+=$ss[0];
$npp = $pp;
$tp[] = $npp;
while($npp<$lim){
$i++;
while($npp<$rss[$i]+1){
foreach($ss as $n){
$npp=$pp+$n;
if($npp>$lim)
break;
if($npp<=$rss[$i]+1)
$pp = $npp;
$sqrtnpp = sqrt($npp);
$test=true;
foreach($tp as $q){
if($sqrtnpp<$q)
break;
elseif($npp%$q==0){
$test=false;
break;
}
}
if($test){
if($npp<=$sqrtlim)
$tp[] = $npp;
else
$xp[] = $npp;
}
}
if($npp>$lim)
break;
}
if($npp>$lim)
break;
$lrpp=$pp;
$nss = array();
while($pp<($rss[$i]+1)*2-1){
foreach($ss as $n){
$npp=$pp+$n;
if($npp>$lim)
break;
$sqrtnpp=sqrt($npp);
$test = true;
foreach($tp as $q){
if($sqrtnpp<$q)
break;
elseif($npp%$q==0){
$test=false;
break;
}
}
if($test){
if($npp<=$sqrtlim)
$tp[] = $npp;
else
$xp[] = $npp;
}
if($npp%$tp[0]!=0){
$nss[] = $npp-$lrpp;
$lrpp=$npp;
}
$pp=$npp;
}
if($npp>$lim)
break;
}
if($npp>$lim)
break;
$ss=$nss;
$ep[] = $tp[0];
array_shift($tp);
$rss[] = $rss[$i]*$tp[0];
$npp=$lrpp;
}
$i=$nss=$npp=$n=$sqrtnpp=$test=$q=$r=$lrpp=$rss=$ss=$pp=$sqrtlim=0;
$ep = array_reverse($ep);
foreach($ep as $a) $tp[]=$a;
$tp = array_reverse($tp);
foreach($tp as $a) $xp[]=$a;
$ep=$tp=$a=$tt=$lim=0;
return $xp;
}
In my PC i get pretty good results:
Any input is welcome, thanks.