Problem 3 - Largest Prime Factor

Soru

13195 sayısının asal bölenleri 5, 7, 13 ve 29'dur.

Öyleyse 600851475143 sayısının en büyük asal böleni nedir?


Çözüm

Bu soru itibariyle asal sayı algoritmalarına giriş yapmış oluyoruz. Birçok soruda bize asal sayıları bulan algoritma gerekecek. Araştırma yaptığınızda göreceksiniz ki, birçok asal sayı bulma algoritması var. Bunlardan en popüleri Sieve of Eratosthenes.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Benim bu algoritma için kullandığım kod şu şekilde. El altında bulunmasında fayda var, ileride bolca lazım olacak.

Sieve of Eratosthenes

static ArrayList SieveOfEratosthenes(int PrimeLimit)
        {
            BitArray bitArray = new BitArray(PrimeLimit, true);

            int LastPrime = 1;
            int LastPrimeSquare = 1;

            while (LastPrimeSquare <= PrimeLimit)
            {
                LastPrime++;

                while (!(bool)bitArray[LastPrime])
                    LastPrime++;

                LastPrimeSquare = LastPrime * LastPrime;

                for (int i = LastPrimeSquare; i < PrimeLimit; i += LastPrime)
                    if (i > 0)
                        bitArray[i] = false;
            }

            ArrayList PrimeList = new ArrayList();

            for (int i = 2; i < PrimeLimit; i++)
            {
                if (bitArray[i])
                {
                    PrimeList.Add(i);
                }
            }

            return PrimeList;


Kodlama

Sorunun çözümü ise bundan sonra bir hayli basit bir hal alıyor. Bize verilen sayının kareköküne(*) kadar olan asal sayılara tam bölünüp bölünmediğine bakıyoruz, eğer bölünüyorsa ekrana yazdırıyoruz.
            int AsalLimit = (int)Math.Sqrt(600851475143);
            ArrayList Asallar = SieveOfEratosthenes(AsalLimit);

            foreach (int Asal in Asallar)
            {
                if (600851475143 % Asal == 0)
                {
                    Console.WriteLine(Asal);
                }

            }

* Neden kareköküne kadar baktığımızı düşünmeniz gerekiyor. Bu bize gereksiz işlemlerden kurtulmayı sağlayan önemli bir adım.

Cevap : 71, 839, 1471 ve 6857. 
Çözüm süresi 31ms.