Challenge
This is a solution of Project Euler 72 in Java.
How may proper reduced fractions \$\dfrac{n}{d}\$ are there, where \$n < d \le 10^6\$?
Code
public long solve() {
int limit = 1000000;
int[] phi = IntStream.range(0, limit + 1).toArray();
long result = 0;
for (int i = 2; i <= limit; i++) {
if (phi[i] == i) {
for (int j = i; j <= limit; j += i) {
phi[j] = phi[j] / i * (i - 1);
}
}
result += phi[i];
}
return result;
}
The algorithm is explained in detail here. When I run the above code on my machine, it takes 150ms to get the answer.
I translated this code into Clojure like the below.
(defn solve []
(let [limit 1000000
phi (int-array (range (inc limit)))]
(loop [i 2 acc 0]
(if (= i (aget phi i))
(loop [j i]
(if (<= j limit)
(do (aset phi j (/ (* (aget phi j) (dec i)) i))
(recur (+ j i))))))
(if (< i limit)
(recur (inc i) (+ acc (aget phi i)))
acc))))
This code uses Java array and mutate the value within the array. The algorithm is logically the same. However, when I run this code in repl, it takes over 25 seconds, which is a huge difference from the Java solution.
I expected that the Clojure code slightly slower than Java. But this is not a slight difference. Why is the Clojure code is slow like this. Did I miss something? Or is there other way to do this better?