+128
- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
(defun primes-under (limit &optional (filter-depth (truncate (log limit))))
(labels ((%purge (prefix table depth)
(iter
(for (key value) :in-hashtable table)
(for mul := (* key prefix))
(while (< mul limit))
(when (> depth 0) (%purge mul table (1- depth)))
(remhash mul table))))
(let ((primes (iter
(with p := (make-hash-table))
(for i :from 2 :below limit)
(setf (gethash i p) t)
(finally (return p)))))
(iter
(for (key value) :in-hashtable primes)
(%purge key primes filter-depth)
(finally
(return
(iter
(for (key value) :in-hashtable primes)
(reducing key :by #'+))))))))
Вопрос к знатокам: почему так работает? (у меня чисто случайно получилось)
Для тех, кому влом разбираться:
Задача выше - код из Прожект Ойлер. Нужно найти сумму всех простых чисел меньше 2000000 (двух миллионов).
Методом подбора было установлено, что если из всех чисел меньше N последовательно удалять их произведения N_0 * N_1 * ... * N_m, где m = floor(log(N)), то, по крайней мере на сколько меня хватило посчитать, не-простых чисел не остается.
Вопрос, как связан log(N), и можно ли вообще надеятся на то, что это правило - универсально (например, что степени двойки никогда не будут меньше N).
Запостил: wvxvw,
14 Апреля 2014
bormand 14.04.2014 10:50 # 0
N_0 и т.п. это исходная последовательность 1 2 3 ... или только неудаленные числа?
Что-то алгоритм не совсем понятен, а лисп вкурить не могу ;( Можно псевдокод какой-нибудь?
wvxvw 14.04.2014 12:02 # 0
Но идея должна быть понятна.
wvxvw 14.04.2014 12:07 # 0
wvxvw 14.04.2014 12:23 # 0
Вот, версия с правильным результатом, но не использующая удаление ключей во время итерации (гораздо медленнее).
3.14159265 14.04.2014 11:50 # 0
roman-kashitsyn 14.04.2014 11:58 # 0
3.14159265 14.04.2014 12:01 # +1
roman-kashitsyn 14.04.2014 12:26 # 0
просто не сразу вкурил, что N_m означает простое число с номером m. Опять же, эта формула работает лишь ассимпотически. Если N = 10, к примеру, то ещё не работает. (ln(10) ~= 2.3) Т.е. в практических задачах лучше на этот результат не полагаться.
3.14159265 14.04.2014 14:28 # +2
Тем же Чебышевым были доказаны интервалы флуктаций пи-функции для практических задач и выведены всякие хитрые приближенные формулы. емнип оверхед в 10% покрывает практически все погрешности.
Причем примечательно что сначала пи-функция отклоняется в одну сторону, потом в другую, и только потом приближается к асимптотическому пределу.
3.14159265 14.04.2014 11:56 # +3
Чебышев вывел формулу кол-во простых чисел N/ln(N), она неточная, но по мере N->∞ становится все точнее.
По сути он доказал что на N чисел приходится ln(N) простых.
То есть, да достаточно выпилить делители всех простых до ln(N), чтобы примерно очистить от составных диапазон [1.. N).
http://ru.wikipedia.org/wiki/Теорема_о_распределении_простых_чисел
Хотя я не особо вдуплил алгоритм, но вроде смахивает на решето.
wvxvw 14.04.2014 12:26 # 0
Да, это по-сути решето, ну не совсем, т.как решето гарантирует что все числа будут простыми, а тут только "до определенной глубины", которая задается через log(N).
Abbath 14.04.2014 13:45 # +3
wvxvw 14.04.2014 13:57 # 0
3.14159265 14.04.2014 15:26 # 0
wvxvw 14.04.2014 14:01 # 0
Abbath 14.04.2014 14:07 # +4
bormand 14.04.2014 14:38 # 0
wvxvw 14.04.2014 15:20 # +2
3.14159265 14.04.2014 15:30 # +1
bormand 14.04.2014 16:39 # 0
3.14159265 14.04.2014 16:40 # +2
brutushafens 14.04.2014 16:55 # +8
bormand 14.04.2014 17:07 # +1
LispGovno 14.04.2014 17:10 # +2
bormand 14.04.2014 17:15 # +1
LispGovno 14.04.2014 17:16 # +3
bormand 14.04.2014 17:16 # +1
Abbath 14.04.2014 19:12 # +2
bormand 14.04.2014 19:18 # 0
Даже матов?
Abbath 14.04.2014 19:19 # 0
bormand 14.04.2014 19:22 # +3
По эмоциональной окраске... Ну и попробовать повторить, глядя на китайца. Если уебал с вертушки - значит это было ругательство.
Abbath 14.04.2014 19:25 # 0
eth0 14.04.2014 19:52 # +1
Есть мнение, что эмоциональная окраска у нас с ними различается.
wvxvw 14.04.2014 19:37 # +4
Вообще, первое ощущение от Китая: примерно, как в первых сериях звездныx воин, в каком-нибудь баре с инопланетянами.
Abbath 14.04.2014 18:40 # +2
bormand 14.04.2014 18:58 # +3
laMer007 14.04.2014 19:07 # +5
ps: жалко у меня нет граватара
Abbath 14.04.2014 19:11 # +2
bormand 14.04.2014 19:12 # +2
> ps: жалко у меня нет граватара
Заведи ;)
laMer007 14.04.2014 19:17 # +1
bormand 14.04.2014 19:24 # +1
Зачем? Граватар же легко убрать/поменять.
laMer007 14.04.2014 19:32 # +1
bormand 14.04.2014 19:36 # +1
Емнип, просто чтобы мыло совпало на гк и там. И чтобы на гк стояла галочка "юзать граватар". Там же id рисунка это хеш от мыла...
Abbath 14.04.2014 19:10 # +2
bormand 14.04.2014 19:37 # 0
Dummy00001 15.04.2014 21:20 # 0
LispGovno 14.04.2014 17:16 # −1
Тебе вот нельзя такое носить, а Борманду можно. По моему ему почти все можно.
bormand 14.04.2014 17:21 # +3
eth0 14.04.2014 17:36 # +1
3.14159265 14.04.2014 17:39 # 0
?
bormand 14.04.2014 17:43 # +1
inkanus-gray 14.04.2014 21:23 # +4
1024-- 14.04.2014 21:46 # +3
P.S. Недавно хотел написать сервер, который выпиливает комментарии и посты неугодных пользователей, раскрывает заминусованные комментарии, отображает заминусованные посты на главной - в общем, отображает белый и пушистый ГК, который приятно читать.
Но как-то лень стало. Вроде юзерскрипты и так хорошо работают.
inkanus-gray 14.04.2014 21:56 # +4
guest 14.04.2014 22:11 # 0
inkanus-gray 15.04.2014 00:20 # +1
guest 15.04.2014 00:25 # 0
Не работает код.
inkanus-gray 15.04.2014 00:32 # +1
guest 15.04.2014 00:39 # 0
inkanus-gray 15.04.2014 00:43 # +1
guest 15.04.2014 00:57 # 0
inkanus-gray 15.04.2014 01:26 # +2
Только зачем?
wvxvw 15.04.2014 00:42 # +1
Упс, я видимо не понял вопрос. Самый последний кусок - это ж вроде nginx конфигурация, не?
WGH 15.04.2014 00:52 # 0
Как-то не похоже.
inkanus-gray 15.04.2014 01:16 # 0
eth0 14.04.2014 18:51 # +1
Когда проще заблочить http://www.gravatar.com/avatar/787e4db09e7f549efecd75e189856682
P.S. Емнип, я так уже блочил чью-то. Кажется, Кузи, Во Времена, Которые Были Очень Давно.
bormand 14.04.2014 18:52 # +1
roman-kashitsyn 14.04.2014 19:16 # +4
небось счастливая морда люра
bormand 14.04.2014 19:27 # 0
eth0 14.04.2014 19:54 # +6
3.14159265 14.04.2014 21:02 # 0
Кстати а у кого-то схоронились линки7
wvxvw 14.04.2014 19:05 # +2
bormand 14.04.2014 19:13 # +1
wvxvw 14.04.2014 19:32 # +1
Abbath 14.04.2014 20:08 # +1
wvxvw 14.04.2014 20:12 # +1
bormand 14.04.2014 20:18 # +2
Кстати, а на твиторе ограничение в 128 символов из-за того, что база не давала сделать больше varchar(128), а блобы авторы не осилили?
laMer007 14.04.2014 20:19 # +1
1024-- 14.04.2014 20:29 # +2
> база не давала сделать больше varchar(128)
Так у них же 140 символов. Видимо, подумали над проблемой и свою базу разработали, которая смогла в varchar(140)
inkanus-gray 14.04.2014 21:30 # +5
На самом деле в SMS укладывается 140 семибитных символов, а если код хотя бы одного символа не укладывается в семь бит, то SMS отправляется в двухбайтной кодировке (UCS-2, UTF-16 или какая-то их модификация, уже не помню). В итоге реальный лимит получается 66 символов.
Создатели же Твиттера лоханулись и сделали лимит в 140 юникодных символов всегда. Ага, если будет хотя бы одна буква не из ASCII, то твит в SMS не пролезет. Правда, это никого не волнует, потому что Твиттером через SMS никто не пользуется.
guest 15.04.2014 02:46 # +3
Abbath 14.04.2014 20:38 # 0
eth0 14.04.2014 20:44 # +3
А мне нравятся люди, которые не могут в микроблоггинг. Да, это в их "свитере" можно наблюдать (и читать снизу вверх) по шесть-семь (десять - личный наблюдаемый рекорд) отрывков сообщения.
Если читать их сверху вниз, то возникает устойчивое ощущение наблюдения за больным с афазией или даже шизофазией.
guest 15.04.2014 00:58 # 0
inkanus-gray 15.04.2014 01:35 # 0
Подменить на что-то другое сложнее, потому что можно только менять фон у блочных элементов или добавлять голый текст.
eth0 15.04.2014 20:28 # +1
1024-- 14.04.2014 20:08 # +1
bormand 14.04.2014 17:40 # +7
brutushafens 14.04.2014 17:44 # +2
Abbath 14.04.2014 18:41 # +1
guest 15.04.2014 02:48 # 0
inkanus-gray 15.04.2014 07:02 # 0
Побочные эффекты Адблока видел. Там слишком много правил, ломающих функционал сайтов. Приходится копаться и удалять.
guest 15.04.2014 07:54 # 0
>ам слишком много правил, ломающих функционал сайтов.
Почему я этого не замечал?
inkanus-gray 15.04.2014 08:53 # +1
А костыли для костылиса называются расширениями.
guest 15.04.2014 09:19 # 0
Abbath 15.04.2014 10:40 # +1
guest 15.04.2014 10:48 # 0
Просто, блядь. Все тормозит и глючит, иди выясняй, какая сука виновата.
Это КОСТЫЛЬ
Abbath 15.04.2014 10:50 # 0
А как добавлять функциональность в браузер? Патчами?
bormand 15.04.2014 10:56 # 0
АКТИВИКСАМИ же.
guest 15.04.2014 12:08 # 0
~Хуятчами~ Браузер искаропки должен иметь функиональность хотя бы оперы 6 2002 года (прыщелис в докачку даже не умеет). Дело не том, что для прыщелиса есть плагины. Дело в том, что без них им нельзя пользоваться, а с ними -тормозит.
bormand 15.04.2014 12:09 # +1
Да ну нахуй? Докачивает при обрыве.
Abbath 15.04.2014 13:21 # +1
bormand 15.04.2014 13:33 # 0
У них торрентов нет, вот и едят кактусы с файлопомоек, бедняги.
guest 16.04.2014 00:53 # 0
Припекает рашкобляди. У них нет торрентов. А у нас есть русскоязычные торренты :)
inkanus-gray 15.04.2014 18:05 # 0
Отдельно тонны ненависти к менеджеру загрузок Хрома. Дико раздражает всплывающая хуета внизу, за которую можно случайно зацепить и запустить свежескачанный экзешник, когда это не нужно.
bormand 15.04.2014 18:20 # +1
Сижу на древнем firefox 28.0 без ПЛАГИНОВ окромя флеша, боюсь запускать браузер, которого в системе нет из коробки. Последний раз отпадание загрузки видел пару-тройку лет назад. Нинужно.
wvxvw 15.04.2014 20:29 # 0
За последние лет пять было один или два раза, что файл скачался битым. Один раз это был дистрибутив Убунты, которую я пытался потом поставить в виртуалбокс и очень долго не мог понять, что случилось. Потом вспомнил про МД5.
Менеджер закачек в последний раз видел в однатысячадевятсот-каком-то году.
guest 15.04.2014 20:34 # 0
bormand 15.04.2014 20:50 # +2
С делфи то? Да никак, забыли о ней как о страшном сне.
brutushafens 16.04.2014 17:46 # +1
brutushafens 16.04.2014 17:58 # +2
bormand 16.04.2014 19:58 # 0
Обёрткопроблемы ;)
bormand 15.04.2014 20:49 # 0
Правка - настройки - основные. Всегда выдавать запрос на сохранение файлов.
> скачиваю curl'ом
wget разве не удобней?
wvxvw 15.04.2014 21:25 # 0
wget разве не удобней?
Да одинаково. Я просто не помню как кукис / пост запрос послать с wget, а иногда нужно.
eth0 15.04.2014 21:31 # 0
В это время прогрессивное человечество изобрело FlashGot.
wvxvw 15.04.2014 21:57 # +1
bormand 16.04.2014 00:28 # 0
Эмакс не умеет сёрфить по инету и качать файлы? Печалька.
wvxvw 16.04.2014 08:21 # 0
eth0 16.04.2014 17:25 # 0
FlashGot + wget, никаких проблем, офицер.
wvxvw 16.04.2014 17:32 # +2
Ну зачем мне ГУИ говно, в котором ни навигация, ни копирование не работают по-человечески?
Я огнелисом пользуюсь исключительно* потому, что в нем есть киснейл и Ф7. Какой мне смысл "дополнять" его какой-то херней, которая эти удобства отменяет.
* - Ну не только, еще и настройки шрифтов удобные.
eth0 16.04.2014 18:54 # 0
Ну так стоило бы начать с того, что мсье знает толк в извращениях.
Моё основное возражение было к
> Иногда угнетает на столько, что начинаю загрузку, потом копирую УРЛ, прерываю загрузку и скачиваю curl'ом уже туда, куда нужно.
Потому что это какой-то вид мазохизма.
wvxvw 16.04.2014 19:37 # 0
guest 16.04.2014 00:54 # 0
Охбля, IE6 скачивал файл во временную папку, а потом копировал его в нужную. На больших файлах подолгу хрустел винтом.
>Дико раздражает всплывающая хуета внизу, за которую можно случайно зацепить и запустить свежескачанный экзешник, когда это не нужно.
Он там по одному клику запускается без вопросов?
guest 15.04.2014 12:10 # 0
bormand 15.04.2014 10:34 # 0
guest 15.04.2014 10:49 # 0
bormand 15.04.2014 10:54 # 0
> Чем меньше ПЛАГИНОВ, тем лучше
Это да, поэтому я никогда их не ставил, даже адблок.
guest 15.04.2014 12:09 # 0
bormand 15.04.2014 18:24 # 0
Да ну. Чем бы реклама не тешилась, лишь бы новые окна не открывала.
guest 16.04.2014 03:26 # 0
bormand 15.04.2014 10:58 # +5
chtulhu 15.04.2014 08:36 # 0
плагин для параноиков сливает данные
bormand 15.04.2014 10:36 # +2
Настоящий плагин для параноиков должен:
- поставляться только в исходниках;
- быть настолько простым, чтобы его можно было прочесть и понять;
- обновляться только вручную.
Все остальное - замаскированный анальный зонд.
inkanus-gray 15.04.2014 18:08 # 0
2. Распаковываем xpi/crx/oex — внутри только код на js, причём необфусцированный. Можно смело считать, что это опенсорс.
bormand 15.04.2014 18:26 # +4
Но ведь он может внезапно обновиться, спиздить данные, а потом внезапно обновиться и стать невинной овечкой :)
inkanus-gray 15.04.2014 19:15 # +6
1024-- 15.04.2014 21:23 # 0
Если в манифесте хроморасширения добавить прав, то хром при его обновлении спросит пользователя, включать ли эту дерзкую хрень с новыми правами, которые в прошлый раз пользователь не давал.
Никто не знает, как подобное происходит с юзерскриптами в Tampermonkey/Greasemonkey?
bormand 15.04.2014 22:02 # +1
Ультиматум Обозревателя Интернета
bormand 16.04.2014 00:05 # 0
Ключевое слово. Если права не поменялись - не спросит. А у гхостери и адблока всяко уже есть права на перехват контента и хттп запросы на их сервер...
guest 16.04.2014 03:26 # 0
1024-- 16.04.2014 09:37 # 0
Права расширения (кроме краткого вопроса хрома "Разрешить расширению похищать ваши данные, воровать и убивать?") можно увидеть, распаковав его, найдя в каталоге с расширениями, или в ко-ко-консолечке от имени расширения посмотрев chrome.app.getDetails(), если у расширения работает фоновая страница, или есть browser action.
Как-то так. Но я особо не копал, может что-нибудь очевидное упустил.
guest 16.04.2014 00:57 # +1
bormand 15.04.2014 20:52 # +2
Кстати, само название plug-in как-бы намекает нам...
Abbath 15.04.2014 10:39 # 0
laMer007 14.04.2014 18:33 # +2
wvxvw 14.04.2014 17:17 # 0
wvxvw 14.04.2014 17:19 # +1
Abbath 14.04.2014 18:38 # +1
guest 15.04.2014 00:24 # 0
http://2ch.hk/s/res/957647.html
guest 16.04.2014 08:29 # 0