Просто о простых числах (быстрый инкрементный метод вычисления простых чисел)

[dlinyj]

Я так понимаю, что автор «изобрёл» Решето Эратосфена

[eandr_67]

Постскриптум статьи столь шедеврален, что приведу отрывок из него без комметариев:

решетом Эратосфена вычисляют диапазоны простых чисел или просто проверяют отдельные числа на простоту. Но когда нужна их полная последовательность, то думать необходимо в примерно таком ключе как описано выше.
Но решето все равно перебирает все числа, пытаясь делить на них тестируемое число.

[xndr]

Я. может, заблуждаюсь, но, мне казалось, что никому уже не интересны простые числа, помещающиеся в long.

[alez13]

Я продемонстрировал алгоритм, как по мне, то он масштабируем в разных измерениях и завернуть многобайтные числа в простые функции операций с ними — задача решаемая для тех, кому это нужно. Кроме того, алгоритм можно переделать под линейные массивы структур данных и дальше все зависит от скорости процессора и объема памяти. Операции в алгоритме — просты, так что процессор не обязан быть сложным.

[alez13]

Вероятно вы не заметили сути. Хеш-таблицы не усложняют, а ускоряют аналогично индексам в таблицах БД. Ограничения алгоритма не в проблемах с производительностью, а цепочка чисел заканчивается там, где у вас заканчивается память. Необходимо хранить слой данных для промежуточных вычислений, этот слой данных растет соизмеримо списку уже найденных простых чисел.

[alez13]

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

[Kirhgoff]

Вот я тут вам нагуглил www.codesdope.com/blog/article/prime-numbers-using-sieve-algorithm-in-c

[alez13]

Что будет с таким алгоритмом, когда N надо наращивать?
и как будет выглядеть результат?
«для каждого очередного… помечает кратные ему» это как минимум вложенный цикл, это не похоже на O(1)
вы собираетесь хранить трилионные массивы булевых значений чтобы проверять большие числа на простоту?
В описанном мной алгоритме простота определяется наличием не в toppings, а в primes. Toppings хранит промежуточные вычисления для дальнейшего расширения диапазона N без необходимости проделывать прежнюю работу с нуля. Если я не ошибаюсь, то третью таблицу (с не простыми числами) хранить не обязательно, она может быть использована при необходимости.
Получая пару ключ-значение мы запоминаем и обратную пару значение-ключ, это и дает нам требуемую индексацию для быстрой проверки есть число в нашем диапазоне или нет.
И как не упирайтесь, а при наращивании диапазона хеш-адресация выигрывает.

[alez13]

Ключ в toppings — непростое число из еще недосчитанного диапазона чисел. например, когда мы нашли простое число 2, мы получаем ключ топпинга 2*2 — ближайшее непростое число имеющее множителем найденную двойку. Значение в toppings — это массив множителей, из которых состоит ключ. Так как 2*2 = 4 в toppings сперва запишется 4=>2. Что значит, что 4 состоит из одной или более двоек.
Когда алгоритм досчитает до 4, то из топпингов эта пара переносится в spectres (непростые числа — спектры множителей).
Следующим непростым числом будет 6, а накопленный для него в таблице топпингов спектр простых множителей будет содержать массив 6 => [2, 3], по достижении счетчиком этот спектр переедет в spectres.
В таблице toppings возникают пары число — массив множителей. Потом, не смотря на то, что они переносятся, эта таблица имеет естественную тенденцию к росту, хоть и не экспоненциальному, но неограниченному, поскольку предела нашего счета нет.
И кстати когда мы перестаем считать, у нас остается некоторый достигнутый порог range. Если запомнить его и сохранить нетронутой таблицу топпингов, то как я уже подмечал выше — можно продолжить считать с того места, на котором остановились. Что дает удобство считать до необходимого числа по мере возникающих потребностей основной программы, которой эти простые числа нужны. Скажем так — lazy calculation.

[tbl]

А зачем вы spectres храните, если потом нигде не используете? И внутренний цикл не параллелится, т.к. использует один и тот же расшаренный ресурс toppings для проверки значения по ключу, вставки записей и модификации массива в значении. Все тело цикла — одна сплошная критическая секция.

[alez13]

Кроме вычисления списка простых чисел, алгоритм попутно определяет спектры непростых чисел. Они считаются в процессе выполнения алгоритма и могут быть сохранены. Как только топпинг переезжает в спектры, для дальнейших вычислений он нам не нужен.
Скажем, я должен был показать возможность, но если спектры не нужны, то расходовать память ни к чему.

[malkovsky]

«для каждого очередного… помечает кратные ему» это как минимум вложенный цикл, это не похоже на O(1)

Внутренний цикл действительно не O(1), при нахождении простого k внутренний цикл делает (n-k*k)/k итераций. Вероятность, что число k является протым — это k/ln(k). Дальше немного базового матана и вы получаете оценку для базового решета Эратосфена O(n loglog(n)).

Есть более оптимальная реализация со сложностью O(n), о ней даже в прошлом году писали на хабре

P. S. alez13 Вы потратили время на изложения своего потока мыслей не удосужившись до это сделать минимальные действию по изучению вопроса (поискать в гугл, ну или на хотя бы на хабре). Это основная причина, почему вашу статью приняли в штыки.

[tbl]

Справедливости ради .keySet() создает вьюху и делает это только 1 раз для мапы, и ее создание имеет сложность O(1), эта вьюха типа Set, вызов .contains() у которой тоже O(1). Но создавать keySet() только для вызова contains() — это моветон, да.

Поиск ключа в хэшмапе все-таки имеет амортизированную алгоритмическую стоимость O(1). И при переполнении бакета мапа рехэшируется, (и не знаю, как в андроиде, но в java 8+, после определенного размера мапы, бакеты из линейного списка после превышения заданной длины превращаются в бинарные деревья). И да, ваши опасения, что будут заняты только четные бакеты, не оправдываются, т.к. хэшкод ключа скрэмблится с помощью ксоров и битовых сдвигов таким образом, чтобы как можно больше старших битов влияло на значение младших.

[alez13]

Нет, давайте проясним. Я скромно делюсь знаниями и не претендую на изобретение нового алгоритма. Я указал на сильные стороны, заслуживающие внимания и если кто-то не найдет ощутимых слабых сторон, то он непременно воспользуется знаниями.

[Kirhgoff]

Да, очень любопытный способ проверять, что ключ в мапе. Я сто лет на джаве не писал, но у HashMap вроде есть метод containsKey, чем он не подошел?

[alez13]

Он бы подошел, если бы пришел в голову вовремя, когда я «говнокодил» :)
Тем лучше для примера, он принципов алгоритма не разрушает.

[Deosis]

С ускорением я бы поспорил, так как элементарный поиск говорит, что даже простой перебор может обработать 10 миллионов чисел за 1:23
А более быстрые версии просеивают миллиард за 8 секунд на PII-350

[zmeysss]

Абсолютно верно. Вот если бы алгоритм автора работал с числами хотя бы порядка 10^50, он бы имел смысл и ценность.

[tronix286]

Алгоритм автора плохо ложится на 8051 с 64-мя байтами памяти…

[zmeysss]

Только не решето, а HashMap Эратосфена.

[tbl]

Простые числа до 1 500 000 за полторы минуты… ну ок, быстро, наверно? Проверил в однопотоке на Core i7-6600U: простой наивный перебор с делением дает 600мс при сборке для таргета «unoptimized + debuginfo»: перебор простых чисел среди нечетных, пока не встретит первое простое число, превышающее 1 500 000

сам код

fn main() {
    println!("{}", Primes::Init.find(|&p| p > 1_500_000).unwrap());
}

enum Primes {
    Init,
    Collect(Vec<u64>),
}

impl Iterator for Primes {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        match self {
            Init => {
                *self = Collect(Vec::new());
                Some(2)
            }
            Collect(primes) => match primes.last() {
                None => {
                    primes.push(3);
                    Some(3)
                }
                Some(max_prime) => {
                    let mut next_possible_prime = max_prime + 2;
                    loop {
                        for prime in primes.iter() {
                            let quad_prime = prime * prime;
                            if quad_prime > next_possible_prime {
                                primes.push(next_possible_prime);
                                return Some(next_possible_prime);
                            }
                            if quad_prime == next_possible_prime || next_possible_prime % prime == 0
                            {
                                break;
                            }
                        }
                        next_possible_prime += 2;
                    }
                }
            },
        }
    }
}

[Neusser]

не знаю, что у вас за телефон, но 96 секунд совсем не повод для гордости. Простенький, не самый оптимальный, алгоритм с использованием деления (медленного, ага), реализованный мной на питоне (медленном, ага) для решения задачек из проекта Эйлера создает список из простых чисел от 2 до 3_000_000 за 15 сек (xperia x compact).

[alez13]

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

[Deosis]

Раз вам важны цифры, то вот сравнение с решетом Эратосфена:

BenchmarkDotNet=v0.12.0, OS=Windows 7 SP1 (6.1.7601.0)
Intel Core i5-3550 CPU 3.30GHz (Ivy Bridge), 1 CPU, 4 logical and 4 physical cores
Frequency=3215400 Hz, Resolution=311.0033 ns, Timer=TSC
  [Host]     : .NET Framework 4.7.2 (4.7.3468.0), X86 LegacyJIT
  DefaultJob : .NET Framework 4.7.2 (4.7.3468.0), X86 LegacyJIT

|      Method |   Bound |           Mean |         Error |        StdDev |
|------------ |-------- |---------------:|--------------:|--------------:|
| Eratosphene |    1000 |       5.934 us |     0.0155 us |     0.0130 us |
|      Alez13 |    1000 |     298.417 us |     5.7851 us |     5.4114 us |
| Eratosphene |   10000 |      75.459 us |     0.3982 us |     0.3530 us |
|      Alez13 |   10000 |   4,209.570 us |    69.5983 us |    61.6971 us |
| Eratosphene |  100000 |     839.022 us |     9.7805 us |     9.1487 us |
|      Alez13 |  100000 |  65,320.950 us | 1,276.4281 us | 1,910.4974 us | 
| Eratosphene | 1000000 |   8,885.445 us |    66.3289 us |    62.0441 us |
|      Alez13 | 1000000 | 910,547.832 us | 6,954.9097 us | 6,165.3463 us |

[alez13]

Дают ли сравниваемые алгоритмы одинаковый результат? Я имею в виду, объем выходных данных, оформлен так же? Или вы сравниваете алгоритм получения одномерного массива бинарных данных (просто указывая признак простоты для индекса элемента) с алгоритмом, на выходе которого хеш мапы, в которых помимо простых чисел, также собираются массивы простых множителей?
Присмотритесь, возможно вы где-то лукавите и не были объективны, демонстрируя 100-кратное превосходство над инкрементным методом вычисления, сравнивая его с закрытым от посторонних глаз исходным кодом.

[Deosis]

Вариант алгоритма с вычислением делителей для каждого числа работает всего в 3 раза медленнее и требует в 32 раза больше памяти.
Но он все ещё в 33 раза быстрее и компактнее вашего.

[tbl]

Похоже, что этот алгоритм не исправить, здесь простое умножение заменено на сложение в цикле, что сразу дает множитель *n к алгоритмической сложности и к требованию по памяти. Простым распараллеливанием это не ускорить. Никто не ускоряет умножение двух чисел распараллеливанием сложения.