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

@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 дал хороший.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@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 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,878
	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