1 / 4
Mar 2013

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.

  • created

    Mar '13
  • last reply

    Mar '13
  • 3

    replies

  • 658

    views

  • 2

    users

  • 1

    link

Your PC is much faster than the judge. Your algorithm is too slow. You are generating all of the primes up to 10^9, which is far too much. The problem asks you to find all of the primes between n and m, use that to your advantage.

Ok, leaving that asside is this the best way to read from stdin with PHP? Or is there a faster way?