Рубрика «решето Эратосфена»

в 11:15, , рубрики: python, ruby, большие целые числа, рекурсия, решето Эратосфена

Несколько алгоритмов на трех языках программирования

Возьмём несколько простых задач и посмотрим, как с ними справляются якобы умерший lisp и современные python и ruby. Сравнивать будем скорость работы, а также компактность и читаемость кода. Тестируем на компьютере с процессором Intel Core i3 2.93 GHz и памятью 14 ГБ. Используем интерпретаторы Lisp SBCL 2.3.2,  Python 3.12.4, Ruby 3.3.3. Автор сразу  хочет заметить: он не пытался придумать или найти самые эффективные алгоритмы; целью являлось именно сравнение работы одинаковых алгоритмов на разных языках. Вот что получилось.

Действительные числа

Читать полностью »

в 12:23, , рубрики: математика, последовательности, простые числа, решето Эратосфена, скатерть Улама
Большие простые числа: вес последовательностей - 1

Посмотрите на эту картинку. Она называется «скатерть УламаЧитать полностью »

в 13:07, , рубрики: C#, Алгоритмы, битовый массив, высокая производительность, математика, оптимизация, простые числа, решето Эратосфена, теория чисел, числовые алгоритмы

image

Самый известный алгоритм для нахождения всех простых чисел, не больших заданного, – решето Эратосфена. Он замечательно работает для чисел до миллиардов, может быть, до десятков миллиардов, если аккуратно написан. Однако каждый, кто любит развлекаться с простыми числами, знает, что их всегда хочется иметь под рукой как можно больше. Как-то раз мне для решения одной задачи на хакерранке понадобилась in-memory база данных простых чисел до ста миллиардов. При максимальной оптимизации по памяти, если в решете Эратосфена представлять нечетные числа битовым массивом, его размер будет около 6 гигабайт, что в память моего ноутбука не влезало. Существует модификация алгоритма, гораздо менее требовательная по памяти (делящая исходный диапазон чисел на несколько кусков и обрабатывающая по одному куску за раз) – сегментированное решето Эратосфена, но она сложнее в реализации, и результат целиком в память все равно не влезет. Ниже предлагаю вашему вниманию алгоритм почти такой же простой, как и решето Эратосфена, но дающий двукратную оптимизацию по памяти (то есть, база данных простых чисел до ста миллиардов будет занимать около 3 гигабайт, что уже должно влезать в память стандартного ноутбука).
Читать полностью »

в 7:53, , рубрики: Baillie–PSW, Алгоритмы, криптография, простые числа, решето Аткина, решето Эратосфена, Тест Люка, Тест Миллера-Рабина, числа мерсенна

Алгоритмы поиска простых чисел - 1«Самое большое простое число 232582657-1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс

Число называется простым, если оно имеет только два различных делителя: единицу и само себя. Задача поиска простых чисел не дает покоя математикам уже очень давно. Долгое время прямого практического применения эта проблема не имела, но все изменилось с появлением криптографии с открытым ключом. В этой заметке рассматривается несколько способов поиска простых чисел, как представляющих исключительно академический интерес, так и применяемых сегодня в криптографии.
Читать полностью »

в 11:48, , рубрики: Crown Sterling, TIME AI, информационная безопасность, квазипростые числв, конференции, криптография, математика, Научно-популярное, решето Эратосфена

Компания, которую выгнали с конференции Black Hat за «псевдонауку», подаёт в суд на организаторов - 1
На иллюстрации: простые числа в числовом пространстве. Кадр из презентации Crown Sterling

Разработчик «точного метода предсказания простых чисел по аналитической методологии квазипростых чисел» (простые числа, у которых нет малых делителей), стартап Crown Sterling подаёт в суд на организаторов хакерской конференции Black Hat USA 2019, где компанию позорно высмеяли, доклад удалили с сайта, а технологию назвали «псевдонаукой».

«Crown Sterling — это инновационный стартап, запускающий новый продукт TIME AI (tm), который представляет собой сдвиг парадигмы в шифровании данных, — сказано в заявлении фирмы. — Мы оплатили участие в Black Hat USA 2019 с намерением представить отрасли информацию о нашей новой технологии. Как и в случае с любой революционной технологией, мы ожидали определённой критики от участников отрасли и конкурентов, также присутствовавших на конференции. Black Hat и правила Code of Conduct заверили нас, что к нам отнесутся открыто и справедливо. Этого не произошло», — заявил Джозеф Хопкинс (Joseph Hopkins), главный операционный директор Crown Sterling. Он подчеркнул, что компания строго придерживалась правил Black Hat как для конференции, так и для спонсорских сессий.
Читать полностью »

в 15:26, , рубрики: Алгоритмы, ассимптотика, математика, решето Эратосфена, сложность алгоритма

В комментариях к одному из прошлых постов о решете Эратосфена был упомянут этот короткий алгоритм из Википедии:

Алгоритм 1:

1: для i := 2, 3, 4, ..., до n: 
2:  если lp[i] = 0:
3:       lp[i] := i
4:       pr[] += {i}
5:   для p из pr пока p ≤ lp[i] и p*i ≤ n:
6:       lp[p*i] := p
Результат:
 lp - минимальный простой делитель для кажого числа до n
 pr - список всех простых до n.

Алгоритм простой, но не всем он показался очевидным. Главная же проблема в том, что на Википедии нет доказательства, а ссылка на первоисточник (pdf) содержит довольно сильно отличающийся от приведенного выше алгоритм.

В этом посте я попытаюсь, надеюсь, доступно доказать, что этот алгоритм не только работает, но и делает это за линейную сложность.
Читать полностью »

в 15:06, , рубрики: Delphi, Алгоритмы, Занимательные задачки, математика, оптимизация, Программирование, простые числа, решето Эратосфена

Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии - 1
(Источник рисунка )

Общеизвестно, что Решето Эратосфена (РЭ) один из древнейших алгоритмов, появившийся задолго до изобретения компьютеров. Поэтому можно подумать, что за века этот алгоритм изучен вдоль и поперек и добавить к нему ничего невозможно. Если посмотреть Википедию – там море ссылок на авторитетные источники, в которых запросто утонуть. Поэтому удивился, когда на днях случайно обнаружил, что вариант, который в Википедии преподносится как оптимальный, можно заметно оптимизировать.
Читать полностью »

в 14:08, , рубрики: Алгоритмы, простые числа, решето Эратосфена

Введение

Одним из алгоритмов для поиска простых чисел является Решето Эратосфена предложенное еще древнегреческим математиком.

Картинка из википедии:

image

Смысл в вычеркивании чисел кратных уже найденным простым. Остающиеся невычеркнутыми в свою очередь являются простыми. Более подробно расписано тут.

Одна из проблем при поиске решетом это объем памяти который надо выделить под фильтруемые числа. Вычеркнутые непростые удаляются уменьшая память, но изначально объем требуется большой.

Для решения используется сегментация (когда память выделяется по кускам) и другие ухищрения (см. тут).

Реализация алгоритма

Алгоритм внизу (написан на java) предполагает минимальный объем памяти — по сути для каждого найденного простого числа мы храним еще одно число — последнее зачеркнутое (наибольшее). Если я правильно оцениваю объем памяти ln(n) — число найденных простых.
Читать полностью »

в 16:06, , рубрики: javascript, алгоритм Евклида, комбинатор неподвижной точки, лямбда-исчисление, ненормальное программирование, решето Эратосфена, функциональное программирование, числа чёрча, метки:

Привет! В этой статье я хочу в очередной раз взглянуть на лямбда-исчисление. Теоретическую сторону вопроса на хабре обсуждали уже множество раз, поэтому взглянем на то, как лямбда-исчисление может выглядеть на практике, например, на языке JavaScript (чтобы примеры можно было выполнять прямо в браузере).
Итак, основная идея: всё есть функция. Поэтому мы ограничим себя очень узким кругом возможностей языка: любое выражение будет либо анонимной функцией с одним аргументом (x => expr), либо вызовом функции (f (x)). То есть весь код будет выглядеть похожим образом:

id = x => x
double = f => x => f (f (x))

Поскольку результатом работы функций будут другие функции, нам понадобится способ интерпретировать результат. Это единственное место, в котором пригодятся нетривиальные возможности JavaScript.
Читать полностью »

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js