Проект Эйлера проблема 3 в Haskell

Question

Я новичок в Хаскеле и пытаюсь решить 3 проблемы из http://projecteuler.net/.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Мое решение:

import Data.List

getD :: Int -> Int
getD x = 
  -- find deviders
  let deriveList = filter (\y -> (x `mod` y) == 0) [1 .. x]
      filteredList = filter isSimpleNumber deriveList
  in maximum filteredList

-- Check is nmber simple
isSimpleNumber :: Int -> Bool
isSimpleNumber x = let deriveList = map (\y -> (x `mod` y)) [1 .. x]
                       filterLength = length ( filter (\z -> z == 0) deriveList)
                       in 
                          case filterLength of
                            2 -> True
                            _ -> False

Я пытаюсь запустить, например:

getD 13195
> 29

Но когда я попробую:

getD 600851475143

Я получаю сообщение об ошибке Исключение: Prelude.maximum: пустой список Почему?

Спасибо @ Барри Браун, я думаю, что должен использовать:

getD :: Integer -> Integer

Но я получаю ошибку:

Couldn't match expected type `Int' with actual type `Integer'
Expected type: [Int]
  Actual type: [Integer]
In the second argument of `filter', namely `deriveList'
In the expression: filter isSimpleNumber deriveList

Спасибо.

Answer 1

Ваша подпись типа ограничивает целочисленные значения примерно до 2 ^ 29. Попробуйте изменить Int на Integer.

Edit:

Я вижу, что вы уже поняли, что вам нужно использовать Integer вместо Int. Вам нужно изменить типы как getD, так и isSimpleNumber, иначе вы получите несоответствие типов.

Также, в общем, если у вас проблемы с типами, просто удалите объявления типов и позвольте Haskell сообщить вам правильные типы.

Main> :t getD
getD :: Integral a => a -> a

Main> :t isSimpleNumber
isSimpleNumber :: Integral a => a -> Bool

Answer 2

После того, как вы нашли ошибку, могу я указать, что ваше решение довольно многословно?В этом случае достаточно простой реализации с использованием грубой силы:

getD n = getD' n 2 where
  getD' n f | n == f = f 
            | n `mod` f == 0 = getD' (n `div` f) f
            | otherwise = getD' n (succ f)  

Answer 3

этот вопрос достаточно прост для грубого решения, но это плохая идея, потому что вся идея проекта euler - это проблемы, о которых вам нужно подумать (см. Конец ответа), поэтому вот некоторыеиз недостатков вашей программы:

сначала используйте rem вместо мода.это более эффективно.

Некоторое математическое мышление должно было сказать вам, что вам не нужно проверять все числа от 1 до x в функции isprime и функции getD, но проверять все числа от квадратного корня до одного(или наоборот) должно быть достаточно.обратите внимание, что в getD вам действительно нужно фильтровать числа между x и квадратным корнем, потому что вы ищете самый большой.

почему вы используете функцию максимума в getD?вы знаете, что список монотонно растет, поэтому вы также можете получить последний.

несмотря на то, что вам нужен только самый большой делитель (который является простым), вы вычисляете список делителей от маленького до большого, заставляя компьютер проверять наличиекаждое значение, если оно является делителем или нет, хотя отбрасывая результат, как только будет найден больший делитель.это должно быть исправлено путем фильтрации списка чисел от x до 1, а не от 1 до x.это заставит компьютер проверять делимость (как я могу это сказать?) для максимально возможного делителя, а не выбрасывать в мусор знание предыдущих проверок.обратите внимание, что эта оптимизация вступает в силу только в том случае, если оптимизируется предыдущая точка, потому что в противном случае компьютер все равно вычислит все делители.

со смешанными предыдущими точками, вы должны были отфильтровать все числа [x, x-1 ..квадратный корень х] и взяли первое.

вы не используете эффективную функцию isPrime.на вашем месте я бы искал библиотечную функцию isprime, которая гарантированно будет эффективной.и есть еще ..

с таким кодом, вы никогда не сможете решить более сложные задачи проекта Эйлера.они предназначены для дополнительного осмысления проблемы (например, замечая, что вам не нужно проверять числа больше из квадратного корня) и написания быстрого и эффективного кода.это цель проекта Эйлера;быть умным в программировании.так что не пропускайте это.