#### Euler Problem 211:

Problem koji tretira djelioce prirodnih brojeva.

Fantastičan post na koji sam naletio riješio je ideju oko zadatka. Nakon pročitanog posta nije bilo teško implemetirati rješenje. Naime, oko divizora i multiplikativnih funkcija mogu se pronaći informacije i na Wikipedii, a suština je i osobini koju posjeduje Sigma funkcija.

Multiplikativne funkcije imaju osobinu da je funkcija proizvoda jednaka proizvodu funkcija:

Ovu osobinu imaju nekoliko značajnih funkcija teorije brojeva poput: Euler Totient funkcija , Möbius Funkcija , Sigma , i druge funkcije.

Kao što je u prethodnim postovima rečeno Sigma funkcije tretira djelioce prirodnog broja n i to:

gdje su djelioci broja .

Zbog multilpikativnosti ove funkcije zadnji izraz možemo napisati kao:

gdje su prosti faktori broja , a , potencije faktora.

Na osnovu zadnjeg izraza možemo pisati:

.

Proširenjem algoritma datog u postu i prilagođavanjem za postavke zadatka imamo:

using System; using System.Collections.Generic; using System.Linq; using System.Text; //Modified code found at http: // comeoncodeon.wordpress.com namespace EulerProblem211 { class Program { static void Main(string[] args) { int N = 64000000; long nprim = (long)Math.Sqrt(N)+1; long[] Sigma0 = new long[N]; long[] Sigma2 = new long[N]; long[] isprime = new long[nprim]; long d, n, p, k, i,e,nom,den; for (n = 2; n < nprim; n++) isprime[n] = 1; //Sieve for Eratosthenes for Prime //Storing the smallest prime which divides n. //If Sigma0[n]=0 it means it is prime number. for (d = 2; d < nprim; d++) { if (isprime[d] > 0) { for (n = d * d; n < nprim; n += d) { isprime[n] = 0; Sigma0[n] = d; } for (; n < N; n += d) Sigma0[n] = d; } } //Applying the formula //Divisor(N)=Divisors(N/p^f(N,p))*(f(N,p)+1) Sigma0[1] = 1; Sigma2[1] = 1; for (n = 2; n < N; n++) { //Prime number if (Sigma0[n] == 0) { Sigma0[n] = 2; Sigma2[n] = n*n+1; } else { //The smallest prime factor of n p = Sigma0[n]; Sigma2[n] += p * p; k = n / p; e = 2; while (k % p == 0) { k /= p; e++; } Sigma0[n] = Sigma0[k] * e; nom = (long)Math.Pow(p, 2 * e) - 1; den =p*p-1; long temp = nom / den; long sol = Sigma2[k]*temp; Sigma2[n] = sol; } } long sum = 0; for (i = 1; i < N; i++ ) { long temp = (long)Math.Sqrt(Sigma2[i]); if (temp * temp == Sigma2[i]) sum += i; } Console.WriteLine(sum); Console.Read(); } } }