Finding prime numbers – sieve of Eratosthenes

Using 2 recent themes from this site, I made for myself the thing that I dreamed of:

/*   */
/*     "mnojiteli",  "tab"   id (int 8) */
$db=mysql_connect("localhost","admin","1234"); mysql_select_db("mnojiteli",$db);
/*  - ,   ,   - "2" */ 
$res=mysql_query("SELECT COUNT(*) FROM tab"); $row=mysql_fetch_row($res);
$tot=$row[0]; if($tot==0){mysql_query("INSERT INTO tab (id) VALUES ('2')");}
/*  ,   -   ,   */
if (isset($_GET['num'])) {$_num = $_GET['num'] + 1;}
else {$_num = 3;} echo $_num."<br>"; $q = mysql_query("SELECT id FROM tab");
/*    $_num   ,  ,     */
while ($d = mysql_fetch_assoc($q)) {extract ($d);
if ($i<1) { $re = $_num % $d['id']; if ($re == 0) {$i=$i+1;};};}
if ($i==0) { $result = mysql_query ("INSERT INTO tab (id) VALUES ('$_num')"); ;}
/*    */
/*   p12.php.     */
<html><body><br><script>
function subm() { document.forms['form1'].submit(); } setTimeout(subm, 1);</script>
<form id="form1" name="form1" method="post" action="<?
echo "p12.php?num=".$_num; ?>">
<input type="button" name="go" id="go" value="Submit" onClick="subm()">
</form></body></html>

Even if you optimize the code, in terms of math calculations, skip the def. numbers, etc. – it will still be slow. It turns out too many requests per unit of time. My computer reached 200’000 in 10 hours. You can, of course, take several numbers, which improved performance, up to 40 minutes, but I want to ask something else…

Is there a way to do similar calculations and write them to a table faster? Well, somehow with a lot of memory consumption)


Answer 1, authority 100%

If I understand you correctly, then you want to find all primesfor example out of 200,000. Try to implement the algorithm Sieve of Eratosthenes. I’ll say right away I didn’t try to implement it myself, but I read that it works quite fast, though I saw all its implementations in C.

As already noted above, it is worth writing to an array, and then to the base. It does not make sense for each found value to make a request to the database to add, this does not give the script performance.


Answer 2, authority 67%

I ran the page on a computer the size of a room – around the number 1’000’000 there were ~ 79 thousand records in the table. The form is very disturbing, you need to replace it with something, in general, what would it be without a button.

Gentlemen, please check out the creative.Works faster than all your examples. But not perfect.

In this file: the Sieve of Eratosthenes algorithm up to 210, iterating by factors of half of the maximum. I think that’s from him and you need to think how to go faster. You need to somehow write all the values ​​of the table into an array, and sort through the factors already from the array, then it will be HUNDREDS times faster.

<?php
 $db = mysql_connect("localhost", "frank", "7450");
 mysql_select_db("slim", $db);
 $res = mysql_query("SELECT COUNT(*) FROM tab");
 $row = mysql_fetch_row($res);
 $tot = $row[0];
 if ($tot == 0) {
   mysql_query("INSERT INTO tab (id) VALUES ('2'), ('3'), ('5'), ('7'), ('11'), ('13'), ('17' ), ('19'), ('23'), ('29'), ('31'), ('37'), ('41'), ('43'), ('47'), ('53'), ('59'), ('61'), ('67'), ('71'), ('73'), ('79'), ('83'), (' 89'), ('97'), ('101'), ('103'), ('107'), ('109'), ('113'), ('127'), ('131' ), ('137'), ('139'), ('149'), ('151'), ('157'), ('163'), ('167'), ('173'), ('179'), ('181'), ('191'), ('193'), ('197'), ('199')");
 }
 if (isset($_GET['num'])) {
   $_num = $_GET['num'];
 } else {
   $_num = 1;
 }
 $cx = $_num * 210;
 echo "obrabotano - " . $cx . "<br>";
 $n001 = $cx + 1;
 $n002 = $cx + 11;
 $n003 = $cx + 13;
 $n004 = $cx + 17;
 $n005 = $cx + 19;
 $n006 = $cx + 23; 
$n007 = $cx + 29;
 $n008 = $cx + 31;
 $n009 = $cx + 37;
 $n010 = $cx + 41;
 $n011 = $cx + 43;
 $n012 = $cx + 47;
 $n013 = $cx + 53;
 $n014 = $cx + 59;
 $n015 = $cx + 61;
 $n016 = $cx + 67;
 $n017 = $cx + 71;
 $n018 = $cx + 73;
 $n019 = $cx + 79;
 $n020 = $cx + 83;
 $n021 = $cx + 89;
 $n022 = $cx + 97;
 $n023 = $cx + 101;
 $n024 = $cx + 103;
 $n025 = $cx + 107;
 $n026 = $cx + 109;
 $n027 = $cx + 113;
 $n028 = $cx + 121;
 $n029 = $cx + 127;
 $n030 = $cx + 131;
 $n031 = $cx + 137;
 $n032 = $cx + 139;
 $n033 = $cx + 143;
 $n034 = $cx + 149;
 $n035 = $cx + 151;
 $n036 = $cx + 157;
 $n037 = $cx + 163;
 $n038 = $cx + 167;
 $n039 = $cx + 169;
 $n040 = $cx + 173;
 $n041 = $cx + 179;
 $n042 = $cx + 181;
 $n043 = $cx + 187;
 $n044 = $cx + 191;
 $n045 = $cx + 193;
 $n046 = $cx + 197;
 $n047 = $cx + 199;
 $n048 = $cx + 209;
 $q001 = mysql_query("SELECT id FROM tab");
 $q002 = mysql_query("SELECT id FROM tab");
 $q003 = mysql_query("SELECT id FROM tab");
 $q004 = mysql_query("SELECT id FROM tab");
 $q005 = mysql_query("SELECT id FROM tab");
 $q006 = mysql_query("SELECT id FROM tab");
 $q007 = mysql_query("SELECT id FROM tab");
 $q008 = mysql_query("SELECT id FROM tab");
 $q009 = mysql_query("SELECT id FROM tab");
 $q010 = mysql_query("SELECT id FROM tab");
 $q011 = mysql_query("SELECT id FROM tab");
 $q012 = mysql_query("SELECT id FROM tab");
 $q013 = mysql_query("SELECT id FROM tab");
 $q014 = mysql_query("SELECT id FROM tab");
 $q015 = mysql_query("SELECT id FROM tab");
 $q016 = mysql_query("SELECT id FROM tab");
 $q017 = mysql_query("SELECT id FROM tab");
 $q018 = mysql_query("SELECT id FROM tab");
 $q019 = mysql_query("SELECT id FROM tab");
 $q020 = mysql_query("SELECT id FROM tab");
 $q021 = mysql_query("SELECT id FROM tab");
 $q022 = mysql_query("SELECT id FROM tab");
 $q023 = mysql_query("SELECT id FROM tab");
 $q024 = mysql_query("SELECT id FROM tab");
 $q025 = mysql_query("SELECT id FROM tab");
 $q026 = mysql_query("SELECT id FROM tab");
 $q027 = mysql_query("SELECT id FROM tab");
 $q028 = mysql_query("SELECT id FROM tab");
 $q029 = mysql_query("SELECT id FROM tab");
 $q030 = mysql_query("SELECT id FROM tab");
 $q031 = mysql_query("SELECT id FROM tab");
 $q032 = mysql_query("SELECT id FROM tab");
 $q033 = mysql_query("SELECT id FROM tab");
 $q034 = mysql_query("SELECT id FROM tab");
 $q035 = mysql_query("SELECT id FROM tab");
 $q036 = mysql_query("SELECT id FROM tab");
 $q037 = mysql_query("SELECT id FROM tab");
 $q038 = mysql_query("SELECT id FROM tab");
 $q039 = mysql_query("SELECT id FROM tab");
 $q040 = mysql_query("SELECT id FROM tab");
 $q041 = mysql_query("SELECT id FROM tab");
 $q042 = mysql_query("SELECT id FROM tab");
 $q043 = mysql_query("SELECT id FROM tab");
 $q044 = mysql_query("SELECT id FROM tab");
 $q045 = mysql_query("SELECT id FROM tab");
 $q046 = mysql_query("SELECT id FROM tab");
 $q047 = mysql_query("SELECT id FROM tab");
 $q048 = mysql_query("SELECT id FROM tab");
 while ($d001 = mysql_fetch_assoc($q001)) {
   extract($d001);
   if ($i001 < 1) {
     $x001 = $n001 / $d001['id'];
     $t001 = $x001 - $d001['id'];
     if ($t001 >= 0) {
       $re001 = $n001 % $d001['id'];
       if ($re001 == 0) {
         $i001 = $i001 + 1;
       }
     }
   }
 }
 while ($d002 = mysql_fetch_assoc($q002)) {
   extract($d002);
   if ($i002 < 1) {
     $x002 = $n002 / $d002['id'];
     $t002 = $x002 - $d002['id'];
     if ($t002 >= 0) {
       $re002 = $n002 % $d002['id'];
       if ($re002 == 0) {
         $i002 = $i002 + 1;
       }
     }
   }
 }
 while ($d003 = mysql_fetch_assoc($q003)) {
   extract($d003);
   if ($i003 < 1) {
     $x003 = $n003 / $d003['id'];
     $t003 = $x003 - $d003['id'];
     if ($t003 >= 0) {
       $re003 = $n003 % $d003['id'];
       if ($re003 == 0) {
         $i003 = $i003 + 1;
       }
     }
   }
 }
 while ($d004 = mysql_fetch_assoc($q004)) {
   extract($d004); 
if ($ i004 & lt; 1) {
     $ X004 = $ N004 / $ D004 ['id'];
     $ T004 = $ X004 - $ D004 ['id'];
     if ($ T004 & GT; = 0) {
       $ re004 = $ n004% $ D004 ['id'];
       if ($ re004 == 0) {
         $ i004 = $ i004 + 1;
       }
     }
   }
 }
 While ($ d005 = mysql_fetch_assoc ($ Q005)) {
   EXTRACT ($ D005);
   if ($ i005 & lt; 1) {
     $ x005 = $ n005 / $ D005 ['id'];
     $ T005 = $ X005 - $ D005 ['ID'];
     if ($ T005 & GT; = 0) {
       $ re005 = $ n005% $ D005 ['id'];
       if ($ re005 == 0) {
         $ i005 = $ i005 + 1;
       }
     }
   }
 }
 While ($ d006 = mysql_fetch_assoc ($ Q006)) {
   Extract ($ D006);
   if ($ i006 & lt; 1) {
     $ X006 = $ N006 / $ D006 ['id'];
     $ T006 = $ X006 - $ D006 ['ID'];
     if ($ T006 & GT; = 0) {
       $ re006 = $ n006% $ D006 ['id'];
       if ($ re006 == 0) {
         $ i006 = $ i006 + 1;
       }
     }
   }
 }
 While ($ d007 = mysql_fetch_assoc ($ Q007)) {
   EXTRACT ($ D007);
   if ($ i007 & lt; 1) {
     $ X007 = $ N007 / $ D007 ['id'];
     $ T007 = $ X007 - $ D007 ['ID'];
     if ($ T007 & GT; = 0) {
       $ re007 = $ n007% $ D007 ['ID'];
       if ($ re007 == 0) {
         $ i007 = $ i007 + 1;
       }
     }
   }
 }
 While ($ d008 = mysql_fetch_assoc ($ Q008)) {
   EXTRACT ($ D008);
   if ($ i008 & lt; 1) {
     $ X008 = $ N008 / $ D008 ['id'];
     $ T008 = $ X008 - $ D008 ['ID'];
     if ($ T008 & GT; = 0) {
       $ re008 = $ n008% $ D008 ['id'];
       if ($ re008 == 0) {
         $ i008 = $ i008 + 1;
       }
     }
   }
 }
 While ($ d009 = mysql_fetch_assoc ($ Q009)) {
   Extract ($ D009);
   if ($ i009 & lt; 1) {
     $ X009 = $ N009 / $ D009 ['id'];
     $ T009 = $ X009 - $ D009 ['id'];
     if ($ T009 & GT; = 0) {
       $ re009 = $ n009% $ D009 ['id'];
       if ($ re009 == 0) {
         $ i009 = $ i009 + 1;
       }
     }
   }
 }
 While ($ d010 = mysql_fetch_assoc ($ Q010)) {
   Extract ($ D010);
   if ($ i010 & lt; 1) {
     $ x010 = $ n010 / $ d010 ['id'];
     $ T010 = $ x010 - $ D010 ['id'];
     if ($ T010 & GT; = 0) {
       $ RE010 = $ n010% $ d010 ['id'];
       IF ($ RE010 == 0) {
         $ i010 = $ i010 + 1;
       }
     }
   }
 }
 While ($ d011 = mysql_fetch_assoc ($ Q011)) {
   EXTRACT ($ D011);
   if ($ i011 & lt; 1) {
     $ x011 = $ n011 / $ d011 ['id'];
     $ T011 = $ x011 - $ D011 ['id'];
     if ($ T011 & GT; = 0) {
       $ RE011 = $ n011% $ D011 ['id'];
       if ($ RE011 == 0) {
         $ i011 = $ i011 + 1;
       }
     }
   }
 }
 While ($ d012 = mysql_fetch_assoc ($ Q012)) {
   Extract ($ D012);
   if ($ i012 & lt; 1) {
     $ x012 = $ n012 / $ d012 ['id'];
     $ T012 = $ x012 - $ D012 ['id'];
     if ($ T012 & GT; = 0) {
       $ RE012 = $ n012% $ D012 ['id'];
       if ($ RE012 == 0) {
         $ i012 = $ i012 + 1;
       }
     }
   }
 }
 While ($ d013 = mysql_fetch_assoc ($ Q013)) {
   EXTRACT ($ D013);
   if ($ i013 & lt; 1) {
     $ x013 = $ n013 / $ d013 ['id'];
     $ T013 = $ x013 - $ D013 ['id'];
     if ($ T013 & GT; = 0) {
       $ RE013 = $ n013% $ D013 ['id'];
       if ($ RE013 == 0) {
         $ i013 = $ i013 + 1;
       }
     }
   }
 }
 While ($ d014 = mysql_fetch_assoc ($ Q014)) {
   EXTRACT ($ D014);
   if ($ i014 & lt; 1) {
     $ x014 = $ n014 / $ d014 ['id'];
     $ T014 = $ x014 - $ D014 ['id'];
     if ($ T014 & GT; = 0) {
       $ RE014 = $ N014% $ D014 ['id'];
       if ($ RE014 == 0) {
         $ i014 = $ i014 + 1;
       }
     }
   }
 }
 While ($ d015 = mysql_fetch_assoc ($ Q015)) {
   Extract ($ D015);
   if ($ i015 & lt; 1) {
     $ x015 = $ n015 / $ d015 ['id'];
     $ T015 = $ x015 - $ D015 ['id'];
     if ($ T015 & GT; = 0) {
       $ RE015 = $ n015% $ D015 ['id'];
       if ($ RE015 == 0) { 
$i015 = $i015 + 1;
       }
     }
   }
 }
 while ($d016 = mysql_fetch_assoc($q016)) {
   extract($d016);
   if ($i016 < 1) {
     $x016 = $n016 / $d016['id'];
     $t016 = $x016 - $d016['id'];
     if ($t016 >= 0) {
       $re016 = $n016 % $d016['id'];
       if ($re016 == 0) {
         $i016 = $i016 + 1;
       }
     }
   }
 }
 while ($d017 = mysql_fetch_assoc($q017)) {
   extract($d017);
   if ($i017 < 1) {
     $x017 = $n017 / $d017['id'];
     $t017 = $x017 - $d017['id'];
     if ($t017 >= 0) {
       $re017 = $n017 % $d017['id'];
       if ($re017 == 0) {
         $i017 = $i017 + 1;
       }
     }
   }
 }
 while ($d018 = mysql_fetch_assoc($q018)) {
   extract($d018);
   if ($i018 < 1) {
     $x018 = $n018 / $d018['id'];
     $t018 = $x018 - $d018['id'];
     if ($t018 >= 0) {
       $re018 = $n018 % $d018['id'];
       if ($re018 == 0) {
         $i018 = $i018 + 1;
       }
     }
   }
 }
 while ($d019 = mysql_fetch_assoc($q019)) {
   extract($d019);
   if ($i019 < 1) {
     $x019 = $n019 / $d019['id'];
     $t019 = $x019 - $d019['id'];
     if ($t019 >= 0) {
       $re019 = $n019 % $d019['id'];
       if ($re019 == 0) {
         $i019 = $i019 + 1;
       }
     }
   }
 }
 while ($d020 = mysql_fetch_assoc($q020)) {
   extract($d020);
   if ($i020 < 1) {
     $x020 = $n020 / $d020['id'];
     $t020 = $x020 - $d020['id'];
     if ($t020 >= 0) {
       $re020 = $n020 % $d020['id'];
       if ($re020 == 0) {
         $i020 = $i020 + 1;
       }
     }
   }
 }
 while ($d021 = mysql_fetch_assoc($q021)) {
   extract($d021);
   if ($i021 < 1) {
     $x021 = $n021 / $d021['id'];
     $t021 = $x021 - $d021['id'];
     if ($t021 >= 0) {
       $re021 = $n021 % $d021['id'];
       if ($re021 == 0) {
         $i021 = $i021 + 1;
       }
     }
   }
 }
 while ($d022 = mysql_fetch_assoc($q022)) {
   extract($d022);
   if ($i022 < 1) {
     $x022 = $n022 / $d022['id'];
     $t022 = $x022 - $d022['id'];
     if ($t022 >= 0) {
       $re022 = $n022 % $d022['id'];
       if ($re022 == 0) {
         $i022 = $i022 + 1;
       }
     }
   }
 }
 while ($d023 = mysql_fetch_assoc($q023)) {
   extract($d023);
   if ($i023 < 1) {
     $x023 = $n023 / $d023['id'];
     $t023 = $x023 - $d023['id'];
     if ($t023 >= 0) {
       $re023 = $n023 % $d023['id'];
       if ($re023 == 0) {
         $i023 = $i023 + 1;
       }
     }
   }
 }
 while ($d024 = mysql_fetch_assoc($q024)) {
   extract($d024);
   if ($i024 < 1) {
     $x024 = $n024 / $d024['id'];
     $t024 = $x024 - $d024['id'];
     if ($t024 >= 0) {
       $re024 = $n024 % $d024['id'];
       if ($re024 == 0) {
         $i024 = $i024 + 1;
       }
     }
   }
 }
 while ($d025 = mysql_fetch_assoc($q025)) {
   extract($d025);
   if ($i025 < 1) {
     $x025 = $n025 / $d025['id'];
     $t025 = $x025 - $d025['id'];
     if ($t025 >= 0) {
       $re025 = $n025 % $d025['id'];
       if ($re025 == 0) {
         $i025 = $i025 + 1;
       }
     }
   }
 }
 while ($d026 = mysql_fetch_assoc($q026)) {
   extract($d026);
   if ($i026 < 1) {
     $x026 = $n026 / $d026['id'];
     $t026 = $x026 - $d026['id'];
     if ($t026 >= 0) {
       $re026 = $n026 % $d026['id'];
       if ($re026 == 0) {
         $i026 = $i026 + 1;
       }
     }
   }
 }
 while ($d027 = mysql_fetch_assoc($q027)) {
   extract($d027);
   if ($i027 < 1) {
     $x027 = $n027 / $d027['id'];