Возможно и правы. Но решето несложно улучшить для уменьшения памяти - сегментирование. Т.е. считать не сразу весь огромный массив чисел, а по сотне тысяч за раз. Собственно считаю это одним из важных достоинств решета.Alexu007 писал(а):Source of the postВ решете же хранятся все числа, и простые и составные. Только там на позиции простых чисел 1, а составных - 0 (или наоборот). Так что памяти всё же надоДмитрий40 писал(а):Source of the post Объём памяти считается несложно, можно даже без интуиции, 32 бита умножить на 204 миллиона - простых чисел до 2^32 - их достаточно для проверки всех чисел вплоть до 2^64. Т.е. память нужна лишь для хранения простых чисел до sqrt(проверяемое число).байт - чтобы работало боле-мене быстро (заморачивание с битами и тем более с делением памяти на "37" ИМХО сильно уменьшит быстродействие).
Но и это только для чисел размером до(и тогда достаточно этих простых чисел), либо продолжать решето с соответствующим расходом памяти. Или я не прав?
Да, и хранить уже проверенный интервал в виде массива нет нужды - простые числа оттуда уже извлекли, массив больше не нужен.
Т.е. для сегментированного решета алгоритм выглядит как повторяющаяся последовательность шагов: а) инициализировать массив решета; б) для каждого из известных простых чисел вычеркнуть его из всего сегмента; в) пройти по сегменту и выдать все найденные простые числа; г) продвинуть начало сегмента дальше пока не достигнем конца желаемого интервала; д) повторить всё с начала.
Размер сегмента выбирается чтобы помещаться в кэш данных процессора (L2 как компромисс по скорости).
Да, именно так, они не хранятся просто по построению массива битов. Каждые 8 битов (1 байт) хранят информацию о 8-ми возможных простых числах в интервале [n..n+29]. А их максимум 8.folk писал(а):Source of the post Также там вроде как не хранятся делящиеся на 2,3,5.
