Cтраница 1
Метод решета Нрупа, как и его модификация, предложенная А. [1]
Чтобы использовать метод решета, как это делал Эратосфен ( имея только карандаш и бумагу), мы поступаем следующим образом. Причина, по которой мы не трогаем четные числа, заключается в том, что, кроме 2, среди них нет простых чисел. [2]
Рассмотрите задачу программирования метода решета - алгоритма D-для двоичной ЭВМ в случае, когда табличные позиции для модуля т - заполняют не точно целое число слов памяти. [3]
В шаге 5 с помощью метода решета мы найдем большой делитель, в то время как с помощью деления будет найден маленький делитель; если повезет, число п будет полностью разложено на простые множители за приемлемое время. [4]
Характеристические векторы полезны в ряде случаев метода решета, которые обсуждаются в разд. Вообще их полезность вытекает из их компактности, существования простого фиксированного соотношения между i и адресом t - го разряда и возможности при таком представлении очень легко исключать элементы. Действительно, все примеры из разд. [5]
Адгезию пленки определяют по ГОСТ 15140 - 69 методом решет -: чатых надрезов. [6]
Нужно помнить, однако, что поиск с возвращением и метод решета представляют собой только общие методы. Непосредственное их применение обычно ведет к алгоритмам, время работы которых недопустимо велико. Современный уровень быстродействия ЭВМ практически не позволяет производить исчерпывающий поиск в множестве, состоящем более чем из 108 элементов. Поэтому для того, чтобы эти методы были полезны, к ним нужно относиться как к схемам, с которыми следует подходить к задаче. Схемы должны быть хорошо приспособлены ( часто это требует большей изобретательности) к конкретной задаче, так чтобы в результате алгоритм годился для практического использования. [7]
Получение множеств Sk напоминает другой метод, применяемый в комбинаторике, а именно метод решета. Он родствен перебору с возвратом, но если перебор с возвратом отбирает подходящие элементы множества, то решето отбрасывает непригодные. Метод решета активно используется в теории чисел; в данной книге он будет рассматриваться в разд. [8]
Сравнить затраты, необходимые для проверки простоты числа 2з - 1 с помощью теста Лукаса и методом решета или методом деления на меньшие простые числа, предполагая, что имеется двоичная ЭВМ с длиной слова w разрядов. Сколько умножений ш-разрядных чисел требуется в тесте Лукаса. [9]
Оказывается, что все известные методы построения таблицы простых чисел - не что иное, как вариации унылого метода решета. Эйлер придумал формулу х2 х 41; для всех х от нуля до 39 эта формула дает простые числа. Другие известные функции дают длинные ряды простых чисел, но ни одна не дает сплошь простые. [10]
Совершенно очевидно, что попытка найти в лоб первый миллион чисел Фибоначчи и выяснить, является ли каждое из них квадратом, совершенно бессмысленна; в то же время методом решета эту задачу можно легко решить за несколько минут. [11]
Этот метод позволяет высеивать последовательности при помощи простых чисел с возрастающим числом выбрасываемых вычетов. Фактически метод большого решета является следствием законов распределения слабо зависимых случайных величин. [12]
Простым числом называется число, которое не имеет других делителей, кроме единицы и самого этого числа. Для решения этой задачи воспользуемся методом решета Эратосфена, идея которого заключается в следующем: сформируем множество М, в которое поместим все числа заданного промежутка. Затем последовательно будем удалять из него элементы, кратные 2, 3, 4 и так далее, до [ л / 2 ] ( целая часть числа), кроме самих этих чисел. [13]
Получение множеств Sk напоминает другой метод, применяемый в комбинаторике, а именно метод решета. Он родствен перебору с возвратом, но если перебор с возвратом отбирает подходящие элементы множества, то решето отбрасывает непригодные. Метод решета активно используется в теории чисел; в данной книге он будет рассматриваться в разд. [14]
Наиболее сильные результаты получают сочетанием методов решета с аналитическими. Метод решета в сочетании с Шнирельмана методом дал возможность эффективно найти значение k такое, что любое натуральное число п4 можно представить суммой не более k простых чисел. [15]