|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Valera Ivanov 2:452/111.555 23 Mar 2002 05:24:52
To : Andrew Doroshev
Subject : Пpостые числа...
--------------------------------------------------------------------------------
AD> И чисел не 63Mб, и даже не 63M*sizeof(long) а немного больше 400Mб, если
AD> хранить именно так, как у Вас.
AD> Файл хранить лучше в виде одно нечётное число - один бит.
AD> Можно даже компактнее, почти вдвое, если заметить, что из каждых 30 чисел
AD> кандидатов в простые только 8
AD> Это 30*K+{1,07,11,13,17,19,23,29}. Прочие делятся на 2,3,5.
ну так можно и далее рассуждать
возьмем 2*3*5*7 = 210 и аналогично и тд, пока не дойдем до разумного с
практической точки зрения предела соотношения
заметь что ты делаешь можно сказать первые 3 (2,3,5) шага
упомянутого тобой метода "Решето Эратосфена" - в таблице (массиве битов, индекс
соответствует нат числу, изначально все биты =1 ) начинаем с 2 (2-й бит
оставляем = 1) зачеркиваем все остальные кратные 2 (те биты 2*i, i>1), переходим
на следующий индекс, бит которого не равен 0, те 3, биты 3*i : =0 и тд до корня
длины массива
те может быть оптимальнее сначала сформировать такое решето, а потом по биту
быстро определять простое число или нет?
AD> Эратосфена
AD> за 6 минут выдаёт результат. Это без записи файла на диск. Если нужна
AD> программа - пишите, поищем.
AD> Andrew Doroshev
AD> + Origin: Demos online service (2:5020/400)
--- GoldED/W32 3.0.1-asa8
* Origin: [Ivanoff Team] [Guitar Music Team] (2:452/111.555)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
