+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
Follow us!
N_0 и т.п. это исходная последовательность 1 2 3 ... или только неудаленные числа?
Что-то алгоритм не совсем понятен, а лисп вкурить не могу ;( Можно псевдокод какой-нибудь?
Но идея должна быть понятна.
Вот, версия с правильным результатом, но не использующая удаление ключей во время итерации (гораздо медленнее).
просто не сразу вкурил, что N_m означает простое число с номером m. Опять же, эта формула работает лишь ассимпотически. Если N = 10, к примеру, то ещё не работает. (ln(10) ~= 2.3) Т.е. в практических задачах лучше на этот результат не полагаться.
Тем же Чебышевым были доказаны интервалы флуктаций пи-функции для практических задач и выведены всякие хитрые приближенные формулы. емнип оверхед в 10% покрывает практически все погрешности.
Причем примечательно что сначала пи-функция отклоняется в одну сторону, потом в другую, и только потом приближается к асимптотическому пределу.
Чебышев вывел формулу кол-во простых чисел N/ln(N), она неточная, но по мере N->∞ становится все точнее.
По сути он доказал что на N чисел приходится ln(N) простых.
То есть, да достаточно выпилить делители всех простых до ln(N), чтобы примерно очистить от составных диапазон [1.. N).
http://ru.wikipedia.org/wiki/Теорема_о_распределении_простых_чисел
Хотя я не особо вдуплил алгоритм, но вроде смахивает на решето.
Да, это по-сути решето, ну не совсем, т.как решето гарантирует что все числа будут простыми, а тут только "до определенной глубины", которая задается через log(N).
Даже матов?
По эмоциональной окраске... Ну и попробовать повторить, глядя на китайца. Если уебал с вертушки - значит это было ругательство.
Есть мнение, что эмоциональная окраска у нас с ними различается.
Вообще, первое ощущение от Китая: примерно, как в первых сериях звездныx воин, в каком-нибудь баре с инопланетянами.
ps: жалко у меня нет граватара
> ps: жалко у меня нет граватара
Заведи ;)
Зачем? Граватар же легко убрать/поменять.
Емнип, просто чтобы мыло совпало на гк и там. И чтобы на гк стояла галочка "юзать граватар". Там же id рисунка это хеш от мыла...
Тебе вот нельзя такое носить, а Борманду можно. По моему ему почти все можно.
?
P.S. Недавно хотел написать сервер, который выпиливает комментарии и посты неугодных пользователей, раскрывает заминусованные комментарии, отображает заминусованные посты на главной - в общем, отображает белый и пушистый ГК, который приятно читать.
Но как-то лень стало. Вроде юзерскрипты и так хорошо работают.
Не работает код.
Только зачем?
Упс, я видимо не понял вопрос. Самый последний кусок - это ж вроде nginx конфигурация, не?
Как-то не похоже.
Когда проще заблочить http://www.gravatar.com/avatar/787e4db09e7f549efecd75e189856682
P.S. Емнип, я так уже блочил чью-то. Кажется, Кузи, Во Времена, Которые Были Очень Давно.
небось счастливая морда люра
Кстати а у кого-то схоронились линки7
Кстати, а на твиторе ограничение в 128 символов из-за того, что база не давала сделать больше varchar(128), а блобы авторы не осилили?
> база не давала сделать больше varchar(128)
Так у них же 140 символов. Видимо, подумали над проблемой и свою базу разработали, которая смогла в varchar(140)
На самом деле в SMS укладывается 140 семибитных символов, а если код хотя бы одного символа не укладывается в семь бит, то SMS отправляется в двухбайтной кодировке (UCS-2, UTF-16 или какая-то их модификация, уже не помню). В итоге реальный лимит получается 66 символов.
Создатели же Твиттера лоханулись и сделали лимит в 140 юникодных символов всегда. Ага, если будет хотя бы одна буква не из ASCII, то твит в SMS не пролезет. Правда, это никого не волнует, потому что Твиттером через SMS никто не пользуется.
А мне нравятся люди, которые не могут в микроблоггинг. Да, это в их "свитере" можно наблюдать (и читать снизу вверх) по шесть-семь (десять - личный наблюдаемый рекорд) отрывков сообщения.
Если читать их сверху вниз, то возникает устойчивое ощущение наблюдения за больным с афазией или даже шизофазией.
Подменить на что-то другое сложнее, потому что можно только менять фон у блочных элементов или добавлять голый текст.
Побочные эффекты Адблока видел. Там слишком много правил, ломающих функционал сайтов. Приходится копаться и удалять.
>ам слишком много правил, ломающих функционал сайтов.
Почему я этого не замечал?
А костыли для костылиса называются расширениями.
Просто, блядь. Все тормозит и глючит, иди выясняй, какая сука виновата.
Это КОСТЫЛЬ
А как добавлять функциональность в браузер? Патчами?
АКТИВИКСАМИ же.
~Хуятчами~ Браузер искаропки должен иметь функиональность хотя бы оперы 6 2002 года (прыщелис в докачку даже не умеет). Дело не том, что для прыщелиса есть плагины. Дело в том, что без них им нельзя пользоваться, а с ними -тормозит.
Да ну нахуй? Докачивает при обрыве.
У них торрентов нет, вот и едят кактусы с файлопомоек, бедняги.
Припекает рашкобляди. У них нет торрентов. А у нас есть русскоязычные торренты :)
Отдельно тонны ненависти к менеджеру загрузок Хрома. Дико раздражает всплывающая хуета внизу, за которую можно случайно зацепить и запустить свежескачанный экзешник, когда это не нужно.
Сижу на древнем firefox 28.0 без ПЛАГИНОВ окромя флеша, боюсь запускать браузер, которого в системе нет из коробки. Последний раз отпадание загрузки видел пару-тройку лет назад. Нинужно.
За последние лет пять было один или два раза, что файл скачался битым. Один раз это был дистрибутив Убунты, которую я пытался потом поставить в виртуалбокс и очень долго не мог понять, что случилось. Потом вспомнил про МД5.
Менеджер закачек в последний раз видел в однатысячадевятсот-каком-то году.
С делфи то? Да никак, забыли о ней как о страшном сне.
Обёрткопроблемы ;)
Правка - настройки - основные. Всегда выдавать запрос на сохранение файлов.
> скачиваю curl'ом
wget разве не удобней?
wget разве не удобней?
Да одинаково. Я просто не помню как кукис / пост запрос послать с wget, а иногда нужно.
В это время прогрессивное человечество изобрело FlashGot.
Эмакс не умеет сёрфить по инету и качать файлы? Печалька.
FlashGot + wget, никаких проблем, офицер.
Ну зачем мне ГУИ говно, в котором ни навигация, ни копирование не работают по-человечески?
Я огнелисом пользуюсь исключительно* потому, что в нем есть киснейл и Ф7. Какой мне смысл "дополнять" его какой-то херней, которая эти удобства отменяет.
* - Ну не только, еще и настройки шрифтов удобные.
Ну так стоило бы начать с того, что мсье знает толк в извращениях.
Моё основное возражение было к
> Иногда угнетает на столько, что начинаю загрузку, потом копирую УРЛ, прерываю загрузку и скачиваю curl'ом уже туда, куда нужно.
Потому что это какой-то вид мазохизма.
Охбля, IE6 скачивал файл во временную папку, а потом копировал его в нужную. На больших файлах подолгу хрустел винтом.
>Дико раздражает всплывающая хуета внизу, за которую можно случайно зацепить и запустить свежескачанный экзешник, когда это не нужно.
Он там по одному клику запускается без вопросов?
> Чем меньше ПЛАГИНОВ, тем лучше
Это да, поэтому я никогда их не ставил, даже адблок.
Да ну. Чем бы реклама не тешилась, лишь бы новые окна не открывала.
плагин для параноиков сливает данные
Настоящий плагин для параноиков должен:
- поставляться только в исходниках;
- быть настолько простым, чтобы его можно было прочесть и понять;
- обновляться только вручную.
Все остальное - замаскированный анальный зонд.
2. Распаковываем xpi/crx/oex — внутри только код на js, причём необфусцированный. Можно смело считать, что это опенсорс.
Но ведь он может внезапно обновиться, спиздить данные, а потом внезапно обновиться и стать невинной овечкой :)
Если в манифесте хроморасширения добавить прав, то хром при его обновлении спросит пользователя, включать ли эту дерзкую хрень с новыми правами, которые в прошлый раз пользователь не давал.
Никто не знает, как подобное происходит с юзерскриптами в Tampermonkey/Greasemonkey?
Ультиматум Обозревателя Интернета
Ключевое слово. Если права не поменялись - не спросит. А у гхостери и адблока всяко уже есть права на перехват контента и хттп запросы на их сервер...
Права расширения (кроме краткого вопроса хрома "Разрешить расширению похищать ваши данные, воровать и убивать?") можно увидеть, распаковав его, найдя в каталоге с расширениями, или в ко-ко-консолечке от имени расширения посмотрев chrome.app.getDetails(), если у расширения работает фоновая страница, или есть browser action.
Как-то так. Но я особо не копал, может что-нибудь очевидное упустил.
Кстати, само название plug-in как-бы намекает нам...
http://2ch.hk/s/res/957647.html