ProjectEuler

[kaipa]

Последние пару недель игрался на Скале с задачами с http://projecteuler.net/, и заодно подсадил на это дело жену. Мне программы писать неинтересно, интересно сделать в пару функциональных строчек в интерпретаторе, благо у Скалы есть консоль, и она хорошо оптимизирует tail-рекурсию. Когда одна из задач в пару скала-строчек не укладывалось, плюнул, и сделал на J в одну. Для J большинство задач просто семечки.

Эйлер 10 (сумма простых чисел, не превышающих 2,000,000):
+/ (#~ <&2000000) p: i.1000000x

Несмотря на то, что уже полгода с J не игрался, принципы все помню, и основное время ушло на поиск глагола для фильтра. Генератор простых чисел в J встроенный, так что по-началу я сгоряча просуммировал все 2,000,000 простых чисел, что тоже заняло всего несколько секунд.

P.S. Скоро мне привезут оригинальные книжки по J, купил остатки на Амазоне, больше там нет.

Comments

[juan-gandhi.livejournal.com]

А если закешировать простые до 1500, то ещё быстрее будет.

[shabunc.livejournal.com]

- Самка, где виноград брали?
Марина от неожиданности так испугалась, что чуть не
выронила сумку.
...
- А там вон, - ответила она, и показала совком в сторону
прилавков, - только там нет больше. Кончился.

[ushastyi.livejournal.com]

Чтобы на делители проверять быстрее? Да, хорошая мысль. Я почти так и делал, только список найденных чисел строился динамически и таскался через рекурсию не самым оптимальным образом, параллельно суммируясь. Было длинно и медленно, вот со злости и сделал через J-brute-force :)

Сейчас попробовал, работает примерно со скоростью J.

scala> val ps = primeStream(2, Nil).take(1500).toList

scala> (2 to 1999999).foldLeft(BigInt(0))( (x: BigInt, y: Int) => x + (if (ps forall (p => y <= p || y % p>0)) y else 0))
res23: scala.math.BigInt = ..censored..

Да еще и красивая симметричная конструкция образовалась:

p => y <= p

:)

[ushastyi.livejournal.com]

Надеюсь, броска не последует? Не отдам :)

P.S. Цитата порадовала, спасибо. Даже перечитать захотелось как-нибудь.