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();

        }
    }
}