Как написать это как одну функцию?

Question

Я иду в проект Euler Q3 и должен получить наибольший простой коэффициент числа. До сих пор я получил пару функций, чтобы вернуть список всех факторов данного номера, но это кажется очень плохим способом сделать это (отчасти потому, что мне нужен только самый большой).

get_factors :: (Integral a) => a -> [a] -> [a] 
get_factors _ [] = [] 
get_factors t (x:xs) 
    | t `mod` x == 0 = x:get_factors t xs 
    | otherwise = get_factors t xs 

factors :: (Integral a) => a -> [a] 
factors x = get_factors x [x,x-1..1] 

> factors 1000 
> [1000,500,250,200,125,100,50,40,25,20,10,8,5,4,2,1] 

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

Можете ли вы указать мне в правильном направлении, как я должен заниматься этим, пожалуйста?

Answer 1

Вы должны попытаться признать, что то, что вы здесь делаете, а именно выбор элементов из списка, удовлетворяющих некоторому условию, является очень распространенным шаблоном. Этот шаблон реализуется функцией filter в прелюдии.

Используя filter, вы можете написать функцию:

factors n = filter (\d -> n `mod` d == 0) [n, n-1 .. 1] 

или, что то же самое, вы можете использовать список понимание:

factors n = [d | d <- [n, n-1 .. 1], n `mod` d == 0] 

Answer 2

Использование функции «запуска» для вызова рекурсивной функции очень распространен в Haskell, так что не бойтесь этого. Чаще всего это было бы записать в виде

f = g someArgument 
    where 
    g = ... 

в вашем случае

factors :: (Integral a) => a -> [a] 
factors x = get_factors [x,x-1..1] 
    where 
    get_factors [] = [] 
    get_factors (y:ys) 
     | x `mod` y == 0 = y : get_factors ys 
     | otherwise  = get_factors ys 

Это сигнализирует читателей вашего кода, который get_factors используется только здесь и больше нигде, и помогает сохранить код в чистоте. Также get_factors имеет доступ к x, что упрощает дизайн.

---

Некоторые другие идеи:

• Это неэффективно пытаться деления всех чисел. В таких проблемах гораздо лучше предварительно вычислить список простых чисел и коэффициент, используя список. Есть many methods, как вычислить такой список, но в образовательных целях я предлагаю вам написать свои собственные (это будет полезно для других проблем Project Euler). Затем вы можете взять список простых чисел, взять часть простых чисел меньше или равную x и попробовать делить их.
• При поиске только для наибольшего фактора вам необходимо выполнить поиск по всем штрихам между 1 и x. Но если x является составным, одним из его факторов должно быть <= sqrt(n). Вы можете использовать это для построения значительно лучшего алгоритма.

Answer 3

Я не думаю, что это очень хорошая идея, чтобы пройти через каждый номер, как [п, п-1 ..], так как проблема говорит 600851475143.

largest_factors :: Integer -> Integer 
largest_factors n = helper n 2 
    where 
     helper m p 
      | m < p^2 = m 
      | m == p = m 
      | m `mod` p == 0 = helper (m `div` p) p 
      | otherwise = helper m (p+1) 

То, что я сделал то, что, как только обнаружилось, что определенное число, скажем p, делит число n, оно просто делит его. Это хорошо работает на моем компьютере. Это дало мне решение в течение секунды.