LINUX.ORG.RU

[Haskell] sumDivisors

 


0

2

Нужна функия суммы делителей натур. числа. Вместо обычного

sumDivisors n = sum [ k | k <- [1..(n `div` 2)], n `mod` k == 0 ]
лучше проверять делители не до n/2, а до sqrt(n/2), причем если нашли делитель k, то n/k тоже будет делителем. Таким способом исчерпываются все делители. Но надо следить, чтобы один делитель не учитывался дважды. На си это выглядит так:
uint sumDivisors(uint n)
{
    uint m = (uint)sqrt(n);
    uint k = 2, sum = 1, tmp;

    for (; k <= m; ++k)
        if (!(n % k)) {
            sum += k;
            if (k != (tmp = n/k))
                sum += tmp;
        }

    return sum;
}

(Замечю, что работает это значительно быстрее перебора всех делителей до n/2, особенно на больших n.) На хаскеле я новичок и написал так:
sumDivisors n = 1 + sum' [ k + m | k <- [2..sq],
                                   n `mod` k == 0,
                                   let t = n `div` k
                                       m = if t /= k then t else 0 ] where
    sq = floor . sqrt . fromIntegral $ n
Можно это как-нибудь попроще, покрасивее записать (не в ущерб скорости)?



Последнее исправление: toady2 (всего исправлений: 2)
Ответ на: комментарий от toady2

OFFTOP. А имеет смысл (в плане скорости) вообще заменять sum на foldl' (+) 0, а nub на toList . fromList (из Data.IntSet)?

toady2
() автор топика
Ответ на: комментарий от toady2

OFFTOP. Не подскажите какую-нибудь статью, где бы описывались основные техники оптимизации в Haskell (foldl', хвостовая рекурсия, toList . fromList, и т. д.)?

toady2
() автор топика
Ответ на: комментарий от unC0Rr

Ясно, спасибо. А что насчёт sum'?

toady2
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.