PHP中的SPOJ素數生成器

Question

我在提交我的解決方案時遇到time limit exceeded錯誤。

<?php 
$stdin = fopen('php://stdin', 'r'); 
$testcase = fgets($stdin); 
$n=1; 
while($n<=$testcase){ 
    $start = fgets($stdin); 
    $end=fgets($stdin); 
    if($start==1) { 
     $start=2; 
    } 
    for($i=$start;$i<$end;$i++){ 
     $flag=0; 
     for($j=2;$j<$i;$j++){ 
      if($i%$j==0){ 
       $flag=1; 
       break; 
      } 
     } 
     if($flag==0){ 
      echo $i."\n"; 
     } 
    } 
    $n++; 
} 

fclose($stdin); 
?> 

請幫我，我堅持用time limit exceeded錯誤，請解釋爲什麼我得到這個錯誤。在我的本地版本中，它顯示了正確的答案。

Answer 1

在第一個for循環，而不是爲循環所有的數字，你可以僅環奇數，因爲2以外的所有的偶數不能是素數。

你可以先用$i+=2 for循環。這可以幫助你減少一些不必要的循環。

更新1：

也在裏面第二的for循環，而不是尋找模將所有的號碼，你可以只存儲計算的素數在數組和檢查，而不是是否$i % calculated prime numbers == 0$i%$j

Answer 2

你解決方案太慢。嘗試稍微修改Eratosthenes篩。修改應該讓您的篩在[開始，年底]區間內才起作用。