Euler Totient ve Eratosthenes’in Kalburu

Project Euler’deki 72. soruyu çözmek için 2’den n’e kadarki sayıların Euler Totient değerlerini hesaplamak gerekiyor. Düz bir mantıkla, n’den küçük veya eşit tüm asal sayıları hesaplayıp her sayı için Euler formülü ile sonucu hesaplamak mümkün. Aşağıda bu yöntemin kodu var;

Burada asal sayıları ayrı bir listede tutmak gerekli değil. Bunun yerine, sieve  listesini kullanarak totient değerini aşağıdaki gibi hesaplayabiliriz;

Her iki kod da hemen hemen aynı complexity değerlerine sahip ama ikincisi daha kısa :).