coding: Нахождение простых чисел

суббота, 28 декабря 2019 г.

Нахождение простых чисел - решето Эратосфена

#php #массивы #алгоритм #математика


Использовав 2 недавних темы с этого сайта, сделал для себя штуку, о которой мечтал:
/* пхп код */
/* создайте у себя базу "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."
"; $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. дописать ниже пхп кода */







Даже если оптимизировать код, в плане вычислений математики, пропускать опр. числа,
и т.п. - это все равно будет медлнено. Получается слишком много запросов за единицу
времени. У меня до 200'000 комп дошел за 10 часов. Можно, конечно, брать по нескольку
чисел, что улучшило производительность, до 40 минут, но спросить хочу другое...
Есть ли способ сделать аналогичные вычисления и запись их в таблицу быстрее? Ну как-нибудь
с большим сжиранием памяти )

Ответы

Ответ 1


Прогнал страницу на компе размером с комнату - в районе числа 1'000'000 в таблице
было ~ 79 тыс. записей. Форма очень мешает, нужно ее чем то заменить, в общем, что
б без кнопки было.
Господа, прошу заценить креатив. Работает быстрее всех ваших примеров. Но не идеально.
В этом файле: алгоритм Решето Эратосфена до 210, перебор на множители половины от
максимума. Думаю вот от него и нужно думать, как быстрее дальше. Нужно как-то записать
все значения таблицы в массив, и перебирать на множители уже из массива, тогда будет
в СОТНИ раз быстрее.
";

  $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 < 1) {
          $x004 = $n004 / $d004['id'];
          $t004 = $x004 - $d004['id'];
          if ($t004 >= 0) {
              $re004 = $n004 % $d004['id'];
              if ($re004 == 0) {
                  $i004 = $i004 + 1;
              }
          }
      }
  }
  while ($d005 = mysql_fetch_assoc($q005)) {
      extract($d005);
      if ($i005 < 1) {
          $x005 = $n005 / $d005['id'];
          $t005 = $x005 - $d005['id'];
          if ($t005 >= 0) {
              $re005 = $n005 % $d005['id'];
              if ($re005 == 0) {
                  $i005 = $i005 + 1;
              }
          }
      }
  }
  while ($d006 = mysql_fetch_assoc($q006)) {
      extract($d006);
      if ($i006 < 1) {
          $x006 = $n006 / $d006['id'];
          $t006 = $x006 - $d006['id'];
          if ($t006 >= 0) {
              $re006 = $n006 % $d006['id'];
              if ($re006 == 0) {
                  $i006 = $i006 + 1;
              }
          }
      }
  }
  while ($d007 = mysql_fetch_assoc($q007)) {
      extract($d007);
      if ($i007 < 1) {
          $x007 = $n007 / $d007['id'];
          $t007 = $x007 - $d007['id'];
          if ($t007 >= 0) {
              $re007 = $n007 % $d007['id'];
              if ($re007 == 0) {
                  $i007 = $i007 + 1;
              }
          }
      }
  }
  while ($d008 = mysql_fetch_assoc($q008)) {
      extract($d008);
      if ($i008 < 1) {
          $x008 = $n008 / $d008['id'];
          $t008 = $x008 - $d008['id'];
          if ($t008 >= 0) {
              $re008 = $n008 % $d008['id'];
              if ($re008 == 0) {
                  $i008 = $i008 + 1;
              }
          }
      }
  }
  while ($d009 = mysql_fetch_assoc($q009)) {
      extract($d009);
      if ($i009 < 1) {
          $x009 = $n009 / $d009['id'];
          $t009 = $x009 - $d009['id'];
          if ($t009 >= 0) {
              $re009 = $n009 % $d009['id'];
              if ($re009 == 0) {
                  $i009 = $i009 + 1;
              }
          }
      }
  }

  while ($d010 = mysql_fetch_assoc($q010)) {
      extract($d010);
      if ($i010 < 1) {
          $x010 = $n010 / $d010['id'];
          $t010 = $x010 - $d010['id'];
          if ($t010 >= 0) {
              $re010 = $n010 % $d010['id'];
              if ($re010 == 0) {
                  $i010 = $i010 + 1;
              }
          }
      }
  }
  while ($d011 = mysql_fetch_assoc($q011)) {
      extract($d011);
      if ($i011 < 1) {
          $x011 = $n011 / $d011['id'];
          $t011 = $x011 - $d011['id'];
          if ($t011 >= 0) {
              $re011 = $n011 % $d011['id'];
              if ($re011 == 0) {
                  $i011 = $i011 + 1;
              }
          }
      }
  }
  while ($d012 = mysql_fetch_assoc($q012)) {
      extract($d012);
      if ($i012 < 1) {
          $x012 = $n012 / $d012['id'];
          $t012 = $x012 - $d012['id'];
          if ($t012 >= 0) {
              $re012 = $n012 % $d012['id'];
              if ($re012 == 0) {
                  $i012 = $i012 + 1;
              }
          }
      }
  }
  while ($d013 = mysql_fetch_assoc($q013)) {
      extract($d013);
      if ($i013 < 1) {
          $x013 = $n013 / $d013['id'];
          $t013 = $x013 - $d013['id'];
          if ($t013 >= 0) {
              $re013 = $n013 % $d013['id'];
              if ($re013 == 0) {
                  $i013 = $i013 + 1;
              }
          }
      }
  }
  while ($d014 = mysql_fetch_assoc($q014)) {
      extract($d014);
      if ($i014 < 1) {
          $x014 = $n014 / $d014['id'];
          $t014 = $x014 - $d014['id'];
          if ($t014 >= 0) {
              $re014 = $n014 % $d014['id'];
              if ($re014 == 0) {
                  $i014 = $i014 + 1;
              }
          }
      }
  }
  while ($d015 = mysql_fetch_assoc($q015)) {
      extract($d015);
      if ($i015 < 1) {
          $x015 = $n015 / $d015['id'];
          $t015 = $x015 - $d015['id'];
          if ($t015 >= 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'];
          $t027 = $x027 - $d027['id'];
          if ($t027 >= 0) {
              $re027 = $n027 % $d027['id'];
              if ($re027 == 0) {
                  $i027 = $i027 + 1;
              }
          }
      }
  }
  while ($d028 = mysql_fetch_assoc($q028)) {
      extract($d028);
      if ($i028 < 1) {
          $x028 = $n028 / $d028['id'];
          $t028 = $x028 - $d028['id'];
          if ($t028 >= 0) {
              $re028 = $n028 % $d028['id'];
              if ($re028 == 0) {
                  $i028 = $i028 + 1;
              }
          }
      }
  }
  while ($d029 = mysql_fetch_assoc($q029)) {
      extract($d029);
      if ($i029 < 1) {
          $x029 = $n029 / $d029['id'];
          $t029 = $x029 - $d029['id'];
          if ($t029 >= 0) {
              $re029 = $n029 % $d029['id'];
              if ($re029 == 0) {
                  $i029 = $i029 + 1;
              }
          }
      }
  }

  while ($d030 = mysql_fetch_assoc($q030)) {
      extract($d030);
      if ($i030 < 1) {
          $x030 = $n030 / $d030['id'];
          $t030 = $x030 - $d030['id'];
          if ($t030 >= 0) {
              $re030 = $n030 % $d030['id'];
              if ($re030 == 0) {
                  $i030 = $i030 + 1;
              }
          }
      }
  }
  while ($d031 = mysql_fetch_assoc($q031)) {
      extract($d031);
      if ($i031 < 1) {
          $x031 = $n031 / $d031['id'];
          $t031 = $x031 - $d031['id'];
          if ($t031 >= 0) {
              $re031 = $n031 % $d031['id'];
              if ($re031 == 0) {
                  $i031 = $i031 + 1;
              }
          }
      }
  }
  while ($d032 = mysql_fetch_assoc($q032)) {
      extract($d032);
      if ($i032 < 1) {
          $x032 = $n032 / $d032['id'];
          $t032 = $x032 - $d032['id'];
          if ($t032 >= 0) {
              $re032 = $n032 % $d032['id'];
              if ($re032 == 0) {
                  $i032 = $i032 + 1;
              }
          }
      }
  }
  while ($d033 = mysql_fetch_assoc($q033)) {
      extract($d033);
      if ($i033 < 1) {
          $x033 = $n033 / $d033['id'];
          $t033 = $x033 - $d033['id'];
          if ($t033 >= 0) {
              $re033 = $n033 % $d033['id'];
              if ($re033 == 0) {
                  $i033 = $i033 + 1;
              }
          }
      }
  }
  while ($d034 = mysql_fetch_assoc($q034)) {
      extract($d034);
      if ($i034 < 1) {
          $x034 = $n034 / $d034['id'];
          $t034 = $x034 - $d034['id'];
          if ($t034 >= 0) {
              $re034 = $n034 % $d034['id'];
              if ($re034 == 0) {
                  $i034 = $i034 + 1;
              }
          }
      }
  }
  while ($d035 = mysql_fetch_assoc($q035)) {
      extract($d035);
      if ($i035 < 1) {
          $x035 = $n035 / $d035['id'];
          $t035 = $x035 - $d035['id'];
          if ($t035 >= 0) {
              $re035 = $n035 % $d035['id'];
              if ($re035 == 0) {
                  $i035 = $i035 + 1;
              }
          }
      }
  }
  while ($d036 = mysql_fetch_assoc($q036)) {
      extract($d036);
      if ($i036 < 1) {
          $x036 = $n036 / $d036['id'];
          $t036 = $x036 - $d036['id'];
          if ($t036 >= 0) {
              $re036 = $n036 % $d036['id'];
              if ($re036 == 0) {
                  $i036 = $i036 + 1;
              }
          }
      }
  }
  while ($d037 = mysql_fetch_assoc($q037)) {
      extract($d037);
      if ($i037 < 1) {
          $x037 = $n037 / $d037['id'];
          $t037 = $x037 - $d037['id'];
          if ($t037 >= 0) {
              $re037 = $n037 % $d037['id'];
              if ($re037 == 0) {
                  $i037 = $i037 + 1;
              }
          }
      }
  }
  while ($d038 = mysql_fetch_assoc($q038)) {
      extract($d038);
      if ($i038 < 1) {
          $x038 = $n038 / $d038['id'];
          $t038 = $x038 - $d038['id'];
          if ($t038 >= 0) {
              $re038 = $n038 % $d038['id'];
              if ($re038 == 0) {
                  $i038 = $i038 + 1;
              }
          }
      }
  }
  while ($d039 = mysql_fetch_assoc($q039)) {
      extract($d039);
      if ($i039 < 1) {
          $x039 = $n039 / $d039['id'];
          $t039 = $x039 - $d039['id'];
          if ($t039 >= 0) {
              $re039 = $n039 % $d039['id'];
              if ($re039 == 0) {
                  $i039 = $i039 + 1;
              }
          }
      }
  }

  while ($d040 = mysql_fetch_assoc($q040)) {
      extract($d040);
      if ($i040 < 1) {
          $x040 = $n040 / $d040['id'];
          $t040 = $x040 - $d040['id'];
          if ($t040 >= 0) {
              $re040 = $n040 % $d040['id'];
              if ($re040 == 0) {
                  $i040 = $i040 + 1;
              }
          }
      }
  }
  while ($d041 = mysql_fetch_assoc($q041)) {
      extract($d041);
      if ($i041 < 1) {
          $x041 = $n041 / $d041['id'];
          $t041 = $x041 - $d041['id'];
          if ($t041 >= 0) {
              $re041 = $n041 % $d041['id'];
              if ($re041 == 0) {
                  $i041 = $i041 + 1;
              }
          }
      }
  }
  while ($d042 = mysql_fetch_assoc($q042)) {
      extract($d042);
      if ($i042 < 1) {
          $x042 = $n042 / $d042['id'];
          $t042 = $x042 - $d042['id'];
          if ($t042 >= 0) {
              $re042 = $n042 % $d042['id'];
              if ($re042 == 0) {
                  $i042 = $i042 + 1;
              }
          }
      }
  }
  while ($d043 = mysql_fetch_assoc($q043)) {
      extract($d043);
      if ($i043 < 1) {
          $x043 = $n043 / $d043['id'];
          $t043 = $x043 - $d043['id'];
          if ($t043 >= 0) {
              $re043 = $n043 % $d043['id'];
              if ($re043 == 0) {
                  $i043 = $i043 + 1;
              }
          }
      }
  }
  while ($d044 = mysql_fetch_assoc($q044)) {
      extract($d044);
      if ($i044 < 1) {
          $x044 = $n044 / $d044['id'];
          $t044 = $x044 - $d044['id'];
          if ($t044 >= 0) {
              $re044 = $n044 % $d044['id'];
              if ($re044 == 0) {
                  $i044 = $i044 + 1;
              }
          }
      }
  }
  while ($d045 = mysql_fetch_assoc($q045)) {
      extract($d045);
      if ($i045 < 1) {
          $x045 = $n045 / $d045['id'];
          $t045 = $x045 - $d045['id'];
          if ($t045 >= 0) {
              $re045 = $n045 % $d045['id'];
              if ($re045 == 0) {
                  $i045 = $i045 + 1;
              }
          }
      }
  }
  while ($d046 = mysql_fetch_assoc($q046)) {
      extract($d046);
      if ($i046 < 1) {
          $x046 = $n046 / $d046['id'];
          $t046 = $x046 - $d046['id'];
          if ($t046 >= 0) {
              $re046 = $n046 % $d046['id'];
              if ($re046 == 0) {
                  $i046 = $i046 + 1;
              }
          }
      }
  }
  while ($d047 = mysql_fetch_assoc($q047)) {
      extract($d047);
      if ($i047 < 1) {
          $x047 = $n047 / $d047['id'];
          $t047 = $x047 - $d047['id'];
          if ($t047 >= 0) {
              $re047 = $n047 % $d047['id'];
              if ($re047 == 0) {
                  $i047 = $i047 + 1;
              }
          }
      }
  }
  while ($d048 = mysql_fetch_assoc($q048)) {
      extract($d048);
      if ($i048 < 1) {
          $x048 = $n048 / $d048['id'];
          $t048 = $x048 - $d048['id'];
          if ($t048 >= 0) {
              $re048 = $n048 % $d048['id'];
              if ($re048 == 0) {
                  $i048 = $i048 + 1;
              }
          }
      }
  }

  if ($i001 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n001')");
  }
  if ($i002 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n002')");
  }
  if ($i003 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n003')");
  }
  if ($i004 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n004')");
  }
  if ($i005 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n005')");
  }
  if ($i006 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n006')");
  }
  if ($i007 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n007')");
  }
  if ($i008 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n008')");
  }
  if ($i009 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n009')");
  }

  if ($i010 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n010')");
  }
  if ($i011 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n011')");
  }
  if ($i012 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n012')");
  }
  if ($i013 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n013')");
  }
  if ($i014 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n014')");
  }
  if ($i015 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n015')");
  }
  if ($i016 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n016')");
  }
  if ($i017 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n017')");
  }
  if ($i018 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n018')");
  }
  if ($i019 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n019')");
  }

  if ($i020 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n020')");
  }
  if ($i021 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n021')");
  }
  if ($i022 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n022')");
  }
  if ($i023 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n023')");
  }
  if ($i024 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n024')");
  }
  if ($i025 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n025')");
  }
  if ($i026 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n026')");
  }
  if ($i027 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n027')");
  }
  if ($i028 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n028')");
  }
  if ($i029 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n029')");
  }

  if ($i030 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n030')");
  }
  if ($i031 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n031')");
  }
  if ($i032 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n032')");
  }
  if ($i033 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n033')");
  }
  if ($i034 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n034')");
  }
  if ($i035 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n035')");
  }
  if ($i036 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n036')");
  }
  if ($i037 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n037')");
  }
  if ($i038 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n038')");
  }
  if ($i039 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n039')");
  }

  if ($i040 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n040')");
  }
  if ($i041 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n041')");
  }
  if ($i042 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n042')");
  }
  if ($i043 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n043')");
  }
  if ($i044 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n044')");
  }
  if ($i045 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n045')");
  }
  if ($i046 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n046')");
  }
  if ($i047 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n047')");
  }
  if ($i048 == 0) {
      $result = mysql_query("INSERT INTO tab (id) VALUES ('$n048')");
  }

  $_num = $_num + 1;
?>













Ответ 2


Если я вас правильно понял, то вы хотите найти все простые числа например из 200
000. Попробуйте реализовать алгоритм Решето Эратосфена. Скажу сразу сам не пробовал
реализовать, но читал что достаточно шустро работает, правда все его реализации видел на C.

Как выше уже заметили стоит записывать в массив, а затем в базу. Не имеет смысла
для каждого найденного значения делать запрос к базе для добавления, это не придаёт
скрипту быстродействия.


Ответ 3


$max = 200000; // максимум
$a = array_fill(1, $max, 1); // заполняем массив чем-то
$max_2 = $max >> 1; // половина от максимума

$i = 2;while($i <= $max_2){ // бежим по множителям
    $j = $i << 1; // =$i*2
    while($j <= $max){ // бежим по массиву
        unset($a[$j]); // вычеркиваем кратности
        $j += $i;
    }
    ++$i;
}

echo implode(', ', array_keys($a)); // что-то делаем с оставшимися числами

Работает шустро, но не оптимально. По-хорошему, надо каждый последующий делитель
брать из оставшихся. И, возможно, есть и более быстрые алгоритмы.

Обновлено

//записываем 1 в БД - ну его нафиг
$i = 2;while(true){
    $j = 2;$i2 = $i >> 1;while($j <= $i2){
        if($i%$j === 0){
            break;
        }
        ++$j;
    }
    if($j === ++$i2){
        // пишем $i в БД
    }
    ++$i;
}
// -комп. удачи.


Ответ 4


Предложу свое решение, оно базируется на "решете Эратосфена" и в нем отсутствует
деление. Есть только поиск по элементам массива.
Алгоритм таков:

имеем хранилище "пар": простое число - следующее после уже проверенного кратное.

Перебираем все числа, начиная с 2.


если в таблице не найдено кратное равное текущему числу - запишем число в таблицу
как простое вместе с его следующим кратным (т.е. n + n)
иначе (найдено кратное равное текущему числу) - всем кратным равным текущему числу
прибавим соответствующие им простые числа.


для решения:
создаем таблицу в MySQL:

create table p
(
    prim int not null default 0, 
    next int not null default 0, 
    primary key(prim), key(next)
);


Создаем хранимую процедуру в MySQL:

CREATE PROCEDURE `insnum`(nn int)
begin
  if(exists(select * from p where next < nn or prim > nn)) then
    select 1 as error;
  else
    if not exists(select * from p where next = nn) then
      insert into p(prim, next) value (nn, nn + nn);
    else
      update p set next = next + prim where next = nn;
    end if;
    select 0 as error;
  end if;
end


процедура работает по описанному алгоритму, за исключением того, что дополнительно
проверяет на попытку вставить числа которые слишком велики или слишком малы. 

Вызываем процедуру для каждого числа (просто по очереди скармливаем все числа процедуре)...

Получаем по одному обращению к базе из php на число (т.е. собственно вызов процедуры)... 

Для увеличения быстродействия можно:


убрать проверку, если точно знаете, что числа будут скармливаться одно за другим.
добавить в таблицу 2-ку как частный случай, скармливать только нечетные числа, каждое
кратное вычислять с шагом 2n: (next + n + n) - с тем, чтобы проверяемые кратные тоже
были нречетными...


Быстродействие не проверял...


Ответ 5


Вычисление массивов по алгоритму "решето Эратосфена" можно сделать быстрым и удобным.
Для этого следует алгоритм сделать ступенчатым, а результат выдавать порциями.
Ограничивая задачу поиском простых чисел до maxint = 2147483647, приходим к максимально
возможному простому делителю в пределах inter=[sqrt(maxint)]=46340.
Имея в распоряжении базовый массив простых чисел в этом диапазоне, можно без труда
реализовать алгоритм "решета Эратосфена" на относительно небольших интервалах, в совокупности
покрывающих весь диапазон от 0 до maxint.
В свою очередь, для получения базового массива указанного размера нужна таблица простых
чисел до [sqrt(inter)]=215.

Программа написана на PHP и содержит следующие функции:


base_sieve(), вычисляющая глобальный массив p_base простых чисел в диапазоне от 2
до inter по классическому алгоритму. Каждый множитель p обрабатывает только те элементы
решета, которые больше p2.
main_sieve($from, $to), имеющая выходным параметром массив простых чисел в диапазоне
от $from до $to включительно. Обработка решета в диапазоне ведётся только в указанном
диапазоне и в обратном порядке, чтобы значение переменной цикла не выходило за пределы
maxint. Разные диапазоны обрабатываются независимо.
print_p($p, $width), которая выводит числовой массив колонками по $width чисел.


Для тестового примера выбран диапазон в 1001 число, ближайшее к maxint.

Текст программы:

$maxint = 2147483647;
$maxval = 214700000;
$inter = 46340;         // =[sqrt($maxint)]

function print_p($arr, $width){
    print("
");
    $prn = $width;
    array_walk($arr, function($item, $key) use(&$prn, $width){
        if ($prn-- == 0){
            print ("
");
            $prn = $width-1;
        }
        print $item." ";
    });
    print("
");
}

function base_sieve(){
    global $inter, $p_base;
    $p0 = array(    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, 211, 223);

    $p_sieve = range(0,$inter-1);
    array_walk($p0, function($item) use(&$p_sieve, $inter) {
        for($j=$item*$item; $j<$inter; $j+=$item) $p_sieve[$j] = 0; 
    });
    $p_sieve[1]=0;
    $p_base = array();
    array_walk($p_sieve, function ($item) use(&$p_base){
        if($item) $p_base[]=$item;
    });
}

function main_sieve($from, $to){
    global $maxint, $p_base;
    if(is_int($from) && is_int($to)) $p_sieve = range($from, $to);
    else exit(1);
    array_walk($p_base, function($item) use(&$p_sieve, $from, $to) {
        if($item*$item <= $to) {
            for($j=$to-$to%$item-$from; $j>=max($item*$item-$from,0); $j-=$item) {
                $p_sieve[$j] = 0;               
            }
        }
    });

    $p = array();
    array_walk($p_sieve, function ($item) use(&$p){
        if($item) $p[]=$item;
    });
    return $p;
}

$p_base=0;
base_sieve();
print ("maxint=$maxint inter=$inter");
printf("
 base_sieve: p_first = %d p_last = %d", reset($p_base), end($p_base));
$p_main = main_sieve($maxint-1000,$maxint);
printf("
 main_sieve: p_first = %d p_last = %d", reset($p_main), end($p_main));
print_p($p_main,10);


Результаты:


maxint=2147483647 inter=46340
base_sieve: p_first = 2 p_last = 46337
main_sieve: p_first = 2147482661 p_last = 2147483647
2147482661 2147482663 2147482681 2147482693 2147482697 2147482739 2147482763 2147482801
2147482811 2147482817 
2147482819 2147482859 2147482867 2147482873 2147482877 2147482921 2147482937 2147482943
2147482949 2147482951 
2147483029 2147483033 2147483053 2147483059 2147483069 2147483077 2147483123 2147483137
2147483171 2147483179 
2147483237 2147483249 2147483269 2147483323 2147483353 2147483399 2147483423 2147483477
2147483489 2147483497 
2147483543 2147483549 2147483563 2147483579 2147483587 2147483629 2147483647 


Диапазон в 1000000 чисел был обработан программой за 27 секунд на компьютере с индексом
производительности 3.5. Увеличение диапазона наталкивается на ограничения по времени
и по памяти. В то же время никто не мешает сбрасывать результаты во внешнюю память
порциями, что позволяет за несколько часов записать все простые числа до maxint=231-1
включительно.

P.S. Объём внешней памяти для записи результатов можно сильно сэкономить, если использовать
полную запись только для первого и последнего (для контроля) чисел на интервале (странице),
а внутри писать полуразности. В частности, для последнего вывода получится запись вида
2147482661 1 9 6 2 21 12 ... 2147483647

coding

Страницы

Поиск по вопросам

суббота, 28 декабря 2019 г.

Нахождение простых чисел - решето Эратосфена

Ответы

Ответ 1

Ответ 2

Ответ 3

Ответ 4

Ответ 5

Комментариев нет:

Отправить комментарий

Страницы

Поиск по вопросам

суббота, 28 декабря 2019 г.

Нахождение простых чисел - решето Эратосфена

Ответы

Ответ 1

Ответ 2

Ответ 3

Ответ 4

Ответ 5

Комментариев нет:

Отправить комментарий

суббота, 28 декабря 2019 г.