Euler Problem 234: Semidivisible numbers

Solution: Ovo je jedan od onih problema kod kojih “Brute-Force” rješenje ne ide. Prvo što mi je palo na pamet je da se izdvoje prosti brojevi iz kalkulacije. Medjutim, to dodatno stvara problem jer se na početku broj mora provjeravati da li je prost. Za prvih nekoliko stotina brojeva ide brzo ali poslije to dugo traje a čitav proces je užasno spor.

Druga varijanta koja je došla je da se keširaju svi prosti brojevi manji od korijena zadanog broja+1 prost broj, odnosno UPS(n). Da, ali iteracija do 999966663333, je užasno spora. Dodatna optimizacija koda je da se iterira kroz proste brojeve, kojih je poprilično mali broj do miliona oko 80 000, pa da se onda između kvadrata susjednih prostih brojeva provjerava uslov zadatka. Ovaj algoritam je poprilično brz, i može se dodatno optimizirati, jer sad možemo umjesto iteracije uzimati brojeve redom koji su djeljivi sa prvim prostim brojem, a s drugim nisu i obrnuto. S tom optimizacijom se dobija rješenje u par sekundi.

Implementacija:

namespace EulerProblem234
{
    class Program
    {
        static List<long> primes = new List<long>();
        static void Main(string[] args)
        {
            long sum = 0;
             long maxn = 999966663333L;
           // long maxn = 1000;
            long primeCount = usp(maxn);
            for (int i = 2; i <= primeCount; i++)
                if (IsPrime(i))
                    primes.Add(i);

            for (int i = 0; i < primes.Count - 1; i++)
            {
                long p1 = primes[i];
                long p2 = primes[i + 1];

                long n1max = p2 * p2;
                long n2min = p1 * p1;

                long n1 = p1 * p1 + p1;
                long n2 = p2 * p2 - p2;

                while (true)
                {
                    if (n1 < maxn)
                    {
                        if (n1 < n1max)
                        {
                            long r = n1 % p2;
                            if (r != 0 )
                                 sum += n1;
                        }
                    }
                    if (n2 < maxn)
                    {
                        if (n2 > n2min)
                        {
                            long r = n2 % p1;
                            if (r != 0 )
                                 sum += n2;

                        }
                    }

                    if (n2 <= n2min && n1 >= n1max)
                        break;

                    n2 -= p2;
                    n1 += p1;

                }
            }
            //End
            Console.WriteLine("Sum semidivisable numbers less than {0} is {1} ", maxn, sum);
            Console.WriteLine("Pres any key to continue...");
            Console.Read();
        }
        static long usp(long n)
        {
            long root = (long)Math.Ceiling(Math.Sqrt(n));
            for (long i = root; i < n; i++)
                if (IsPrime(i))
                    return i;
            return 0;
        }
        static bool IsPrime(long n)
        {
            for (int i = 2; i * i <= n; i++)
                if (n % i == 0)
                    return false;
            return true;
        }
    }
}