3

Использовав 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."<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>

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

Есть ли способ сделать аналогичные вычисления и запись их в таблицу быстрее? Ну как-нибудь с большим сжиранием памяти )

3
  • Возможно. Но не до бесконечности, а пока комп не выдержит. Обновил сообщение.
    – ling
    11 авг 2011 в 14:22
  • 1
    Вообще, наверное, запуск php через web-сервер - не лучшая идея. Кто мешает php запускать как скрипт? Т.е. php <название_файла_скрипта_php>. По идее ограничений на работу будет существенно меньше, но не уверен. И если я правильно понимаю - Вам нужно искать простые числа? Так переименуйте вопрос. "Неделящиеся" числа это немного некорректный термин.
    – gecube
    11 авг 2011 в 14:38
  • Объясните мне, недалёкому, в чём задача состоит, заставить SQL-сервер находить простые числа? Просто если искать простые числа естественным путём, что-то типа секунды уходит на проверку всех чисел до миллиона 4 авг 2013 в 14:18

5 ответов 5

3

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

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

2

Прогнал страницу на компе размером с комнату - в районе числа 1'000'000 в таблице было ~ 79 тыс. записей. Форма очень мешает, нужно ее чем то заменить, в общем, что б без кнопки было.

Господа, прошу заценить креатив. Работает быстрее всех ваших примеров. Но не идеально.

В этом файле: алгоритм Решето Эратосфена до 210, перебор на множители половины от максимума. Думаю вот от него и нужно думать, как быстрее дальше. Нужно как-то записать все значения таблицы в массив, и перебирать на множители уже из массива, тогда будет в СОТНИ раз быстрее.

<?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 < 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;
?>

<html>
<body>
<br>
<script>
function subm() { document.forms['form1'].submit(); } 
setTimeout(subm, 1);
</script>
<form id="form1" name="form1" method="post" action="<?php
  echo "p12.php?num=" . $_num;
?>">
<input type="button" name="go" id="go" value="Submit" onClick="sub()">
</form>
</body>
</html>
2
  • быстрее моего метода, хоть и не на много. 12 авг 2011 в 7:05
  • А что, в php массивы уже отменили? или они такие тормозные, что ручное разворачиваение дает мегаприрост скорости?
    – KoVadim
    8 дек 2015 в 8:29
2
$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;
}
// -комп. удачи.
5
  • Не совсем оно! Точнее совсем не то, что ищу. ((( 1. Искать по половине от максимума - математическая функция. Вопрос не про нее. 2. Вычеркивание кратных чему то чисел - аналогично п.1. 3. Максимум, он где то рядом с числом бесконечность, не нужно его указывать. 4. Заполнять массив в ручную - ну, тогда можно код и не писать. Можно ли создать массив, который будет пополняться в месте с базой, и без обновления страницы? 11 авг 2011 в 12:45
  • Простите, не понял вопроса. Какой принцип вы хотите реализовать? Можно ведь сформировать массив и записать его в БД - это не проблема.
    – ling
    11 авг 2011 в 13:16
  • Идеально было бы такое: 1. чтение всех записей из таблицы, запись в массив; 2. определение последней записи; 3. последняя запись + 1; 4. последняя запись + 1000; 5. искать в промежутке от п3-п4 записи, не делящиеся ни на одно число из массива п1; 6. найденное в п5 записать в таблицу; 7. повторять пока комп не расплавиться, господа, хелп ми! 11 авг 2011 в 13:33
  • Сомневаюсь, что ваша задача относится к php. Так как у вас тут вычисления занимают много времени, скрипт отвалится по таймауту. Можно дать скрипту больше времени на выполнение, но зачем - пхп для такого не предназначен?
    – ling
    11 авг 2011 в 13:58
  • 1
    я не спрашиваю чем лучше убивать медведя, граблями или двустволкой. я спрашиваю куда граблями его ткнуть более эффективно. 11 авг 2011 в 14:32
2

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

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

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

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

для решения: создаем таблицу в 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 на число (т.е. собственно вызов процедуры)...

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

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

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

2

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

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

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

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

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

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

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

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("<br> base_sieve: p_first = %d p_last = %d", reset($p_base), end($p_base));
$p_main = main_sieve($maxint-1000,$maxint);
printf("<br> 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

4
  • (оффтопик) вы алгоритмист, посмотрите на это.
    – VladD
    1 дек 2015 в 22:01
  • Да. "Russian woodpecker". 1 дек 2015 в 22:07
  • ? Гугл по словосочетанию «Russian woodpecker» выдаёт только фильм.
    – VladD
    1 дек 2015 в 22:11
  • google.com.ua/… 1 дек 2015 в 22:15

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.