Что ж, продолжим знакомство с F#, а заодно решение задач с Проекта Эйлера, начатое мною в предыдущем посте. Сегодня я рассмотрю сразу несколько задач из этого проекта, связанных с простыми числами. В первой десятке таковых три штуки, вот на них и посмотрим.
В этих примерах мы будем как и прежде использовать только функциональные аспекты языка, для окончательного, так сказать, закрепления. А о том, как использовать F# в императивной и объектно-ориентированной парадигме, я пожалуй расскажу отдельно, в следующий раз.
Итак, у нас есть три задачи:
10. The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.
3. The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
7. By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^(th) prime is 13. What is the 10001^(st) prime number?
В первой задаче мы изгаляться не будем, не для того собственно собрались, а решим самым что ни на есть обычным решетом Эратосфена. В качестве домашнего задания можно попробовать реализовать решето Аткина.
После нескольких чисток и улучшений у меня получился следующий код:
Внутренняя рекурсивная функция next, принимающая список, сравнивает его с тремя возможными шаблонами. Первый из них, пустой список, нужен исключительно чтобы компилятор не ругался на incomplete pattern matches. На самом деле, сюда наша функция никогда не попадет, а терминальным для нее является второе сравнение.
В этом шаблоне помимо стандартного для работы со списками разделения на голову и хвост (n::tail) используется еще дополнительное условие, которое записано после ключевого слова when. В данном случае оно проверяет, не стало ли наше число достаточно большим (sqrt max), что процедуру отсеивания можно было прекратить и если это так, то выдает наружу оставшийся у нее список. В последнем шаблоне собственно и происходит просеивание, заданное лямбдой.
Поскольку сумма всех простых чисел может быть довольно внушительным числом (а так оно и есть, ответ 142913828922), то мы используем в коде 64-битовые целые int64, и как бы намекаем об этом компилятору, дописывая после констант «L».
В одном случае правда намеками обойтись не удалось, так как пришлось приводить квадратный корень к int64. Кстати до этого пришлось приводить наше число к плавающей точке функцией float, так как sqrt от целого браться не желал. Для программистов C# это выглядит довольно странно. Работает функция не то чтобы очень быстро, но в рамки, очерченные правилами проекта укладывается с запасом.
Вторую из списка задач мы решим величайшим математическим методом всех времен и народов, а именно, методом чайника.
Если вдруг совершенно случайно кто-то не знает, метод описывается следующим анекдотом:
Математик спрашивает у физика: «У тебя есть пустой чайник, кран с водой, и плита. Как согреть чайник?» «Надо налить из крана воды в чайник, зажечь огонь и поставить на него чайник», — отвечает физик. «Отлично! — говорит математик, — а теперь представь, что в чайнике есть вода, а огонь зажжен». «Ну тогда совсем просто», — говорит физик, — «ставим чайник на плиту». «Вот и нет, — говорит математик, — надо вылить воду, потушить огонь и задача сведется к предыдущей».
Вот и мы сводя задачу к предыдущей, построим список всех простых чисел, отфильтруем те, на которые делится заданное число и найдем среди них максимальное. Единственная ценная мысль — искать простые числа надо не до самого числа, а до его квадратного корня. Таким образом имеем код:
На этом примере можно еще раз оценить всю мощь Pipeline. (Как же на русский-то перевести? «Трубопровод» как-то не очень звучит...) Наверняка есть способы и побыстрее решить, без «чайника», может кто что предложит?
Третью задачу, конечно, тоже можно решать с помощью того же кухонного прибора, ну например эмпирическим путем проверив, что найденных нами простых чисел <2M куда больше чем 10001 (да что там, их и в миллионе-то больше), так что достаточно просто без опасений взять 10001-й элемент полученного списка. Но ведь согласитесь, такое решение как-то претит нашему программистскому чувству прекрасного. Очень хочется решить задачу в общем виде.
В итоге размышлений я решил попросту реализовать наивный метод — фильтрация полного списка чисел в соответствии с тестом простоты, применил небольшие оптимизации, и, как, ни удивительно, сработало отлично, да и для 10001-го числа получилось несоизмеримо быстрее чем первый предложенный способ.
Выглядит в моей интерпретации так:
Пожалуй, это самый любопытный пример из всех трех.
Метод Seq.init_infinite задает, как и следует из названия, бесконечную последовательность. Ну да, именно бесконечную. Задается она указанной в скобках лямбдой, в нашем случае тождественной. Бесконечность эта, конечно, виртуальна, ведь на самом деле последовательность в момент определения еще не существует, а будет создана только когда в ней возникнет необходимость, точно так же, как и операции над ней будут проделываться только когда их результаты будут требоваться для дальнейшей работы. Короче говоря, F# поддерживает ленивые вычисления (с помощью добавления перед функцией ключевого слова lazy), а класс Seq обладает такой способностью априори. Тема ленивых вычислений достаточно обширна и сложна, чтобы хоть сколько-то полно осветить ее здесь, поэтому я не буду даже пытаться это сделать. Думаю Google в состоянии предоставить необходимое количество информации по этой теме. Адепты Haskell могут конечно и придраться к моим самопальным определениям, но мне в свою очередь непонятно, что могло в этой статье так заинтересовать адептов Haskell, чтобы дочитать до этого места.
Ну а остальные действия в программе уже вряд ли могут вызвать вопросы. С помощью первых двух фильтров мы оставляем только те элементы, которые нам нужны (большие двух и не делящиеся на два), а последний фильтр применяет тест на простоту.
Вот как-то так.
В этих примерах мы будем как и прежде использовать только функциональные аспекты языка, для окончательного, так сказать, закрепления. А о том, как использовать F# в императивной и объектно-ориентированной парадигме, я пожалуй расскажу отдельно, в следующий раз.
Итак, у нас есть три задачи:
10. The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.
3. The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
7. By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^(th) prime is 13. What is the 10001^(st) prime number?
В первой задаче мы изгаляться не будем, не для того собственно собрались, а решим самым что ни на есть обычным решетом Эратосфена. В качестве домашнего задания можно попробовать реализовать решето Аткина.
После нескольких чисток и улучшений у меня получился следующий код:
#light
let primes max =
let rec next potentialPrimes =
match potentialPrimes with
|[] -> []
|n::tail when n > int64 (sqrt (float max)) -> n::tail
|n::tail -> n :: next (List.filter (fun x -> x % n <> 0L) tail)
next [2L .. max]
primes 2000000L |> List.fold_left (+) 0L |> printfn "%d"
Внутренняя рекурсивная функция next, принимающая список, сравнивает его с тремя возможными шаблонами. Первый из них, пустой список, нужен исключительно чтобы компилятор не ругался на incomplete pattern matches. На самом деле, сюда наша функция никогда не попадет, а терминальным для нее является второе сравнение.
В этом шаблоне помимо стандартного для работы со списками разделения на голову и хвост (n::tail) используется еще дополнительное условие, которое записано после ключевого слова when. В данном случае оно проверяет, не стало ли наше число достаточно большим (sqrt max), что процедуру отсеивания можно было прекратить и если это так, то выдает наружу оставшийся у нее список. В последнем шаблоне собственно и происходит просеивание, заданное лямбдой.
Поскольку сумма всех простых чисел может быть довольно внушительным числом (а так оно и есть, ответ 142913828922), то мы используем в коде 64-битовые целые int64, и как бы намекаем об этом компилятору, дописывая после констант «L».
В одном случае правда намеками обойтись не удалось, так как пришлось приводить квадратный корень к int64. Кстати до этого пришлось приводить наше число к плавающей точке функцией float, так как sqrt от целого браться не желал. Для программистов C# это выглядит довольно странно. Работает функция не то чтобы очень быстро, но в рамки, очерченные правилами проекта укладывается с запасом.
Вторую из списка задач мы решим величайшим математическим методом всех времен и народов, а именно, методом чайника.
Если вдруг совершенно случайно кто-то не знает, метод описывается следующим анекдотом:
Математик спрашивает у физика: «У тебя есть пустой чайник, кран с водой, и плита. Как согреть чайник?» «Надо налить из крана воды в чайник, зажечь огонь и поставить на него чайник», — отвечает физик. «Отлично! — говорит математик, — а теперь представь, что в чайнике есть вода, а огонь зажжен». «Ну тогда совсем просто», — говорит физик, — «ставим чайник на плиту». «Вот и нет, — говорит математик, — надо вылить воду, потушить огонь и задача сведется к предыдущей».
Вот и мы сводя задачу к предыдущей, построим список всех простых чисел, отфильтруем те, на которые делится заданное число и найдем среди них максимальное. Единственная ценная мысль — искать простые числа надо не до самого числа, а до его квадратного корня. Таким образом имеем код:
#light
let num = 600851475143L
let primes max =
let rec next potentialPrimes =
match potentialPrimes with
|[] -> []
|n::tail when n > int64 (sqrt (float max)) -> n::tail
|n::tail -> n :: next (List.filter (fun x -> x % n <> 0L) tail)
next [2L .. max]
num |> float |> sqrt |> int64 |> primes
|> List.filter (fun x -> num % x = 0L) |> List.max |> printfn "%d"
На этом примере можно еще раз оценить всю мощь Pipeline. (Как же на русский-то перевести? «Трубопровод» как-то не очень звучит...) Наверняка есть способы и побыстрее решить, без «чайника», может кто что предложит?
Третью задачу, конечно, тоже можно решать с помощью того же кухонного прибора, ну например эмпирическим путем проверив, что найденных нами простых чисел <2M куда больше чем 10001 (да что там, их и в миллионе-то больше), так что достаточно просто без опасений взять 10001-й элемент полученного списка. Но ведь согласитесь, такое решение как-то претит нашему программистскому чувству прекрасного. Очень хочется решить задачу в общем виде.
В итоге размышлений я решил попросту реализовать наивный метод — фильтрация полного списка чисел в соответствии с тестом простоты, применил небольшие оптимизации, и, как, ни удивительно, сработало отлично, да и для 10001-го числа получилось несоизмеримо быстрее чем первый предложенный способ.
Выглядит в моей интерпретации так:
#light
let isPrime n =
let limit n = int(sqrt (float n)) in
{ 2..limit n } |> Seq.for_all (fun x -> n%x <> 0)
let primes = Seq.init_infinite (fun i -> i)
|> Seq.filter (fun i -> i >= 2)
|> Seq.filter (fun i -> i%2 <> 0)
|> Seq.filter isPrime
primes |> Seq.nth 10000 |> printfn "%d"
Пожалуй, это самый любопытный пример из всех трех.
Метод Seq.init_infinite задает, как и следует из названия, бесконечную последовательность. Ну да, именно бесконечную. Задается она указанной в скобках лямбдой, в нашем случае тождественной. Бесконечность эта, конечно, виртуальна, ведь на самом деле последовательность в момент определения еще не существует, а будет создана только когда в ней возникнет необходимость, точно так же, как и операции над ней будут проделываться только когда их результаты будут требоваться для дальнейшей работы. Короче говоря, F# поддерживает ленивые вычисления (с помощью добавления перед функцией ключевого слова lazy), а класс Seq обладает такой способностью априори. Тема ленивых вычислений достаточно обширна и сложна, чтобы хоть сколько-то полно осветить ее здесь, поэтому я не буду даже пытаться это сделать. Думаю Google в состоянии предоставить необходимое количество информации по этой теме. Адепты Haskell могут конечно и придраться к моим самопальным определениям, но мне в свою очередь непонятно, что могло в этой статье так заинтересовать адептов Haskell, чтобы дочитать до этого места.
Ну а остальные действия в программе уже вряд ли могут вызвать вопросы. С помощью первых двух фильтров мы оставляем только те элементы, которые нам нужны (большие двух и не делящиеся на два), а последний фильтр применяет тест на простоту.
Вот как-то так.
