|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roman Miroshnichenko 2:5020/400 25 Mar 2002 23:22:15
To : Andrew Doroshev
Subject : Re: Пpостые числа... - fido7.ru.algorithms
--------------------------------------------------------------------------------
> О том и речь, что разумный предел - 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 - 50% 1/2 - бзусловно
3 = 1/2*2/3 = 1/3 - совпало
5 = (2-1)/2*(3-1)/3*(5-1)/5 = 4/15 = 26.7% - это уже что-то
(почему не 3/10 = 9/30, а 8/30 ? Да хотя бы потому, что после 5
в интервале 30 ровно 8 простых чисел (7,11,13,17,19,23,29,31)
7 = 4/15*6/7=24/105 = 8/35 = 22.9% - это еще не предел
..
13 = 8/35*10/11*12/13 = 192/1001 = 19.1% можно разумно
тормозить, так как 2*3*5*7*11*13 уже всего лишь 30030
ЗЫ: кстати, благодаря такому отсеиванию и тесту Рабина-Миллера,
я сравнительно быстренько построил все 32-х битные простые числа ,
а оказалось их ровно ровно 203_280_221 штуки, и после определенных
извратов поместилось 220 МБ!
--- ifmail v.2.15dev5
* Origin: A poorly-installed InterNetNews site (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
