Thanks for the formatting tip; I hadn’t taken the time to figure out how to use this site and saw that the code was pretty ugly…
Even though the code I submitted earlier gets the right answer in all versions, there’s some confusion, vestiges of changes in how I wrote it as I was solving the problem. For example, the test for < 10000 in the amicable function isn’t necessary; it’s never going to see an n>=10000 because of the how the main function is written.
Here are improved versions.
C:
#include <stdio.h>
#include <stdlib.h>
int d(int n) {
int n_half=n/2, m, result=1;
for (m=2; m<=n_half; m++)
if ((n % m) == 0)
result += m;
return result;
}
int amicable(int n) {
int dn=d(n), ddn=d(dn);
if ((ddn == n) && (n != dn))
return n;
else
return 0;
}
int main () {
int i, result=0;
for (i=1; i<10000; i++)
result += amicable(i);
printf("%d\n", result);
exit(0);
}
Rust:
fn amicable(n:i32) -> i32 {
let dn=d(n);
let ddn=d(dn);
if (ddn==n) && (n != dn) {
n
} else {
0
}
}
fn d(n: i32) -> i32 {
(2..(n / 2 + 1)).
filter(|m| n % m == 0).
fold(0, |result, i| result + i)
}
fn main () {
let mut result:i32=0;
for i in 1..10000 {
result = result + amicable(i);
}
println!("{}", result);
}
And since a couple of you have gotten Haskell-ey, here’s a Haskell version:
d :: Int -> Int
d n = foldl (\acc m -> if (mod n m)==0; then acc+m; else acc) 1 [2..(div n 2)]
amicable :: Int -> Int
amicable n = if ((d (d n)) == n) && (n /= (d n)); then n ; else 0
main = do print (foldl (\acc n -> acc + (amicable n)) 0 [1 .. 9999])
On my machine, the C version runs in about .16 seconds. The Rust version runs in about .23 seconds, or a little under 44% slower than the C version. The Haskell version runs in about .84 seconds, or 425% slower than the C version.
As I said before, the machine is a Thinkpad X-250, 4 GB memory, 7200 rpm disk, Arch Linux, up-to-date.
