HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Brute-force perfect-number algorithm

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
numberforceperfectalgorithmbrute

Problem

I whipped a reasonably fast brute-force perfect number finding function in Haskell, after seeing a similar thing in mathematica.

It works in under 3 seconds when I search up to 1000, but 10000 is too much.

isDivisor :: Integral a => a -> a -> Bool
isDivisor n a = mod n a == 0

sumDivisors :: Integral a => a -> a
sumDivisors a =
   foldr (\n -> if isDivisor a n then (+ n) else id) 0 [1..(a `div` 2)]

isPerfect :: Integral a => a -> Bool
isPerfect n = n == sumDivisors n

-- The main prime-finding function:
upUntil :: Integral a => a -> [a]
upUntil n = filter isPerfect [1..n]


It certainly isn't the fastest, or the most elegant, but I'm unsure how I can improve it.

I would like to concentrate on the isDivisor function in particular. Is there a more efficient way of checking for divisibility?

Solution

Use backticks

Backticks allow you to put the function name between the values instead of before:

isDivisor n a = mod n a == 0


becomes:

isDivisor n a = n `mod` a == 0


Give less general names

The name upUntil tells nothing about perfect numbers, in a tiny script like this this is no problem, but the habit of meningful names will play yo your advantage in larger scripts

Do not write wrong comments

Comments don't run, but you are not justified to write wrong comments

-- The main prime-finding function:


The function does not find primes.

Code Snippets

isDivisor n a = mod n a == 0
isDivisor n a = n `mod` a == 0
-- The main prime-finding function:

Context

StackExchange Code Review Q#86689, answer score: 7

Revisions (0)

No revisions yet.