note 64973 added to language.types.array

Sophisticated codes have their own cost, the setback in speed. Suppose you want to find primes to a certain number (10000 in the example below) you just look up whether each number is divisible by the primes up to (the floor of) the square root of the number, and examining (if the number is divisible by) all integers from 2 (to the floor of square root of the number) seems to be a mere wast of time. (Once some number can not be divided by 2, it surely can not be divided by 4, for example) So, experienced programmers or mathematicians would code something like: <?php $n=10000; $prime=array(2); for($i=3;$i<$n;$i++) { $uint=sqrt($i); foreach($prime as $p) { if($p>$uint) { $prime[]=$i; break; } if($i%$p==0) break; } } foreach($prime as $p) echo $p." "; } ?> This takes about .87 seconds at my machine. While the seemingly 'stupid' version of this, looking up every interger up to the floor of the square root of each number is coded something like: <?php $n=10000; $prime=array(2,3); for($i=5;$i<$n;$i++) { $uint=floor(sqrt($i)); for($j=2;$j<=$uint;$j++) { if($i%$j==0) break; if($j==$uint) $prime[]=$i; } } foreach($prime as $p) echo $p." "; ?> This takes .08 seconds. Ten times faster than the more sophiscated code! Bear in mind array manipulation takes much longer than we imagine. (The use of array for writing down all of them at the end of the program doesn't harm. I also tried to write down each prime immediately after it is found, it made little difference) ---- Server IP: 66.163.161.117 Probable Submitter: 218.178.156.85 ---- X-Spam-Status: No, hits=3.1 required=5.0 tests=DATE_MISSING,FROM_NO_LOWER autolearn=no version=2.64 ---- Manual Page -- http://www.php.net/manual/en/language.types.array.php Edit -- http://master.php.net/note/edit/64973 Del: integrated -- http://master.php.net/note/delete/64973/integrated Del: useless -- http://master.php.net/note/delete/64973/useless Del: bad code -- http://master.php.net/note/delete/64973/bad+code Del: spam -- http://master.php.net/note/delete/64973/spam Del: non-english -- http://master.php.net/note/delete/64973/non-english Del: in docs -- http://master.php.net/note/delete/64973/in+docs Del: other reasons-- http://master.php.net/note/delete/64973 Reject -- http://master.php.net/note/reject/64973 Search -- http://master.php.net/manage/user-notes.php