Список простых чисел

@freeman86 · Регистрация: 20.07.2016

Студворк — интернет-сервис помощи студентам

Чтобы не плодить темы, решил спросить тут. Вот кусок программы, он на JS, но это не важно. Он должен пропускать простые числа(те, которые делятся без остатка только на 1 и на себя), и записывать в счетчик составные. Сама программа работает, но я всю голову сломал почему она работает! Ведь, как минимум часть i <= Math.sqrt(n) никогда не будет true, так как i всегда будет больше n на единицу...

я в программировании новичек, но вроде бы с циклом for разобрался. А тут что-то непонятное. Во вторых, зачем извлекать корень квадратный...

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
var n = 1
 
search: while (true)
{
  n += 1
 
  for (var i = 2; i <= Math.sqrt(n); i += 1)
  {
    if (n % i == 0) continue search
  }
 
  postMessage(n)
}

Вот описание работы алгоритма автором: В этом файле переменной n присваивается значение 1. Затем запускается бесконечный цикл с увеличением значения n на единицу и проверкой значения «в лоб» на принадлежность к простым числам. При этом тестируются все значения от 1 до корня квадратного из n для проверки, делится ли n на них без остатка. Если сомножитель будет найден, то команда continue тут же останавливает лобовую атаку, поскольку число не является простым, и начинает обработку снова в отношении следующего более высокого значения n.
Но если все возможные сомножители будут протестированы и не будет найден результат с нулевым остатком, то n должно быть простым числом, следовательно, его значение передается функции postMessage, отправляющей сообщение событию onmessage объекта, который установил этот рабочий веб-процесс.
Результат выглядит следующим образом:
Текущее самое большое простое число: 30477191

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

HTML5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<!DOCTYPE html>
<html> <!-- webworkers.html -->
  <head>
    <title>Web Workers</title>
    <script src='OSC.js'></script>
  </head>
  <body>
    Current highest prime number:
    <span id='result'>0</span>
 
    <script>
      if (!!window.Worker)
      {
        var worker = new Worker('worker.js')
 
        worker.onmessage = function (event)
        {
          O('result').innerHTML = event.data;
        }
      }
      else
      {
        alert("Web workers not supported")
      }
    </script>
  </body>
</html>

А это OSC. Если кто захочет запустить посмотреть.

JavaScript
1
2
3
function O(i) { return typeof i == 'object' ? i : document.getElementById(i) }
function S(i) { return O(i).style                                            }
function C(i) { return document.getElementsByClassName(i)                    }

@Shamil1 · 21.10.2017, 14:53

Сообщение от freeman86

Ведь, как минимум часть i <= Math.sqrt(n) никогда не будет true, так как i всегда будет больше n на единицу...

Почему i будет больше n?
n - это число, которое мы проверяем на простоту
i - это числа, которые могут быть делителями числа n

на первой итерации цикла while n равно 2, поэтому во внутренний цикл for мы не зайдём
но, начиная с третьей итерации внешнего цикла, мы будем заходить во внутренний цикл

@freeman86 · 21.10.2017, 22:37 **[ТС]**

Shamil1, а почему мы не зайдем во внутренний цикл for сразу, а только с третьей итерации?

@Shamil1 · 22.10.2017, 00:32

Сообщение от freeman86

а почему мы не зайдем во внутренний цикл for сразу, а только с третьей итерации?

Потому что в начале цикла i = 2. Для n = 2 и n = 3 не выполняется условие "i <= Math.sqrt(n)".

@freeman86 · 22.10.2017, 20:57 **[ТС]**

Это я понимаю. Но если нет захода в for, разве будет заход в if в данном случае? Или сразу после невыполнения i <= Math.sqrt(n) идет выполнение postMessage(n)?

@Shamil1 · 22.10.2017, 23:03

Сообщение от freeman86

Но если нет захода в for, разве будет заход в if в данном случае?

Не будет.

Сообщение от freeman86

Или сразу после невыполнения i <= Math.sqrt(n) идет выполнение postMessage(n)?

Да.

Сообщение от freeman86

Он должен пропускать простые числа

Алгоритм, наоборот, пропускает составные числа.

@freeman86 · 22.10.2017, 23:40 **[ТС]**

При достижении n = 4, i увеличивается на единицу, и таким остается до следующего составного числа, а там увеличивается еще на единицу?

А как, например, с числом 6? В цикле for оно не проходит, так как 3 <= 2.45. Но ведь оно составное, так как 6/1, 6/2 и 6/6 без остатка!

@Shamil1 · 23.10.2017, 13:51

внешний цикл перебирает n - числа, которые мы хотим проверить на простоту
внутренний цикл перебирает i - числа, на которые мы делим проверяемое число
за пределами внутреннего цикла i не определено

для каждого нового n мы сначала устанавливаем i = 2, а потом начинаем увеличивать i на 1, пока оно не станет слишком большим
после этого переходим к следующему n

@freeman86 · 23.10.2017, 20:45 **[ТС]**

Теперь понятно! Значит, после каждой итерации цикла while, с заходом в for, i возвращается на 2 и проверка начинается с 2, а потом возрастает пока не упрется в i <= Math.sqrt(n). Просто я раньше не сталкивался с циклами, вложенными один в другой.

А если бы i была определена за пределами for, например там же, где n, чтобы это изменило?

@Shamil1 · 24.10.2017, 13:54

Сообщение от freeman86

после каждой итерации цикла while, с заходом в for, i возвращается на 2 и проверка начинается с 2, а потом возрастает пока не упрется в i <= Math.sqrt(n)

Да.

Сообщение от freeman86

А если бы i была определена за пределами for, например там же, где n, чтобы это изменило?

В данном случае, нет, так как выполнение цикла начинается с "i = 2".

Вот тут простым языком написано про цикл for:
https://learn.javascript.ru/while-for

@freeman86 · 24.10.2017, 19:51 **[ТС]**

Спасибо! A какой математический смысл i <= Math.sqrt(n)? Зачем извлекать корень из n и сравнивать его с i?

@Shamil1 · 24.10.2017, 21:51

Сообщение от freeman86

Зачем извлекать корень из n и сравнивать его с i?

Мы проверяем, является ли i множителем числа n. То есть, существует ли такое число j, что i * j == n. Так как мы проверяем по порядку, начиная с 2, то нам достаточно искать такие i, что i <= j. Если i > j, то мы раньше найдём j и закончим проверку этого числа n. Меньший из сомножителей не может быть больше квадратного корня из n, поэтому дальше проверять не надо.

@oldnick85 · 28.10.2017, 01:30

Небольшое замечание: i <= Math.sqrt(n) лучше использовать в виде i<= sq_n, а sq_n вычислять перед этим вне цикла, чисто для ускорения работы.

@freeman86 · 28.10.2017, 22:28 **[ТС]**

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

@Shamil1 · 29.10.2017, 15:26

Сообщение от freeman86

а почему так, как вы предлагаете, будет быстрее работать

Math.sqrt(n) будет вычисляться один раз перед внутренним циклом, а не на каждой итерации (при каждой проверке условия). Нормальные компиляторы выполняют эту оптимизацию самостоятельно. Но, вероятно, интерпретатор JavaScript не умеет выполнять такую оптимизацию. Так что совет oldnick85 дал хороший.

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

@freeman86 0 / 0 / 0 Регистрация: 20.07.2016 Сообщений: 98
	21.10.2017, 22:37 [ТС]
	Shamil1, а почему мы не зайдем во внутренний цикл for сразу, а только с третьей итерации? 0

@freeman86 0 / 0 / 0 Регистрация: 20.07.2016 Сообщений: 98
	22.10.2017, 20:57 [ТС]
	Это я понимаю. Но если нет захода в for, разве будет заход в if в данном случае? Или сразу после невыполнения i <= Math.sqrt(n) идет выполнение postMessage(n)? 0

@freeman86 0 / 0 / 0 Регистрация: 20.07.2016 Сообщений: 98
	22.10.2017, 23:40 [ТС]
	При достижении n = 4, i увеличивается на единицу, и таким остается до следующего составного числа, а там увеличивается еще на единицу? А как, например, с числом 6? В цикле for оно не проходит, так как 3 <= 2.45. Но ведь оно составное, так как 6/1, 6/2 и 6/6 без остатка! 0

@Shamil1 Модератор 3137 / 2284 / 469 Регистрация: 26.03.2015 Сообщений: 8,888
	23.10.2017, 13:51
	внешний цикл перебирает n - числа, которые мы хотим проверить на простоту внутренний цикл перебирает i - числа, на которые мы делим проверяемое число за пределами внутреннего цикла i не определено для каждого нового n мы сначала устанавливаем i = 2, а потом начинаем увеличивать i на 1, пока оно не станет слишком большим после этого переходим к следующему n 1

@freeman86 0 / 0 / 0 Регистрация: 20.07.2016 Сообщений: 98
	23.10.2017, 20:45 [ТС]
	Теперь понятно! Значит, после каждой итерации цикла while, с заходом в for, i возвращается на 2 и проверка начинается с 2, а потом возрастает пока не упрется в i <= Math.sqrt(n). Просто я раньше не сталкивался с циклами, вложенными один в другой. А если бы i была определена за пределами for, например там же, где n, чтобы это изменило? 0

@freeman86 0 / 0 / 0 Регистрация: 20.07.2016 Сообщений: 98
	24.10.2017, 19:51 [ТС]
	Спасибо! A какой математический смысл i <= Math.sqrt(n)? Зачем извлекать корень из n и сравнивать его с i? 0

@oldnick85 36 / 34 / 10 Регистрация: 15.07.2017 Сообщений: 128
	28.10.2017, 01:30
	Небольшое замечание: i <= Math.sqrt(n) лучше использовать в виде i<= sq_n, а sq_n вычислять перед этим вне цикла, чисто для ускорения работы. 1

@freeman86 0 / 0 / 0 Регистрация: 20.07.2016 Сообщений: 98
	28.10.2017, 22:28 [ТС]
	oldnick85, а почему так, как вы предлагаете, будет быстрее работать. Мне просто интересно для общего развития. 0