online advertising

Tuesday, June 9, 2015

Haskell 99 Problem 38

Problem

Please find the problem here.

Solution:

The new version is faster on large input, totient 30624700 hangs, while phi 30624700 outputs 12249840 almost instantly.
This can be explained as totient is running the Euclidean algorithm 30624700 times, while phi is doing $ \sqrt {30624700} $ trial divisions only.

No comments :

Post a Comment