|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Doroshev 2:5020/400 25 Mar 2002 22:00:07
To : Valera Ivanov
Subject : Re: Пpостые числа...
--------------------------------------------------------------------------------
Dear Valera Ivanov!
> AD> Файл хранить лучше в виде одно нечётное число - один бит.
> AD> Можно даже компактнее, почти вдвое, если заметить, что из каждых 30 чисел
> AD> кандидатов в простые только 8
> AD> Это 30*K+{1,07,11,13,17,19,23,29}. Прочие делятся на 2,3,5.
>
> ну так можно и далее рассуждать
> возьмем 2*3*5*7 = 210 и аналогично и тд, пока не дойдем до разумного с
> практической точки зрения предела соотношения
О том и речь, что разумный предел - 2*3*5
2 50% 1/2
3 33,(3)% 1/2-1/(2*3)=1/3
5 30% 1/3-1/(2*3*5)=3/10
7 29,52% 3/10-1/(2*3*5*7)=31/105
11 29,48% 31/105-1/(2*3*5*7*11)=227/770
При переходе от 2*3*5 к 2*3*5*7 экономия - пол процента
>
> заметь что ты делаешь можно сказать первые 3 (2,3,5) шага
> упомянутого тобой метода "Решето Эратосфена" - в таблице (массиве битов,
> индекс соответствует нат числу, изначально все биты =1 ) начинаем с 2 (2-й бит
> оставляем = 1) зачеркиваем все остальные кратные 2 (те биты 2*i, i>1),
> переходим на следующий индекс, бит которого не равен 0, те 3, биты 3*i : =0 и
> тд до корня длины массива
Hе надо путать просеивание с хранением.
Речь идёт именно о хранении. А сеять будем все нечётные числа.Или даже с
чётными, но за несколько проходов.
>
> те может быть оптимальнее сначала сформировать такое решето, а потом по биту
> быстро определять простое число или нет?
Hе понял...
Andrew Doroshev
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
