Tag Archives: asal çarpan

Asal Çarpanları Bulma Algoritması

Bir sayıyı oluşturan asal çarpanların nasıl en efektif şekilde bulunabileceğini anlattım bu videoda. Önemli olan iki nokta var; birincisi kontrol edeceğimiz sayıları verilen sayının kareköküne kadar (karekökü dahil) iterasyon ile kontrol etmek ve elimizdeki sayıyı bölebildiğimiz kadar o sayıya bölmek, ikincisi de eğer bu iterasyon sonrası sayımız 1’e eşit olmadıysa (videoda anlattığım 99 örneği gibi) son kalanı da listeye eklemek.

► Asal çarpan nedir? https://tr.wikipedia.org/wiki/Asal_%C3%A7arpan

Asal çarpan, bir sayının asal olan çarpanlarına denir. Örnek olarak 72 sayısının asal çarpanları 2 ve 3’ken (2^3 * 3^2), 4, 6, 8, 9, 12, 18, 24, 36, 72 asal çarpan değildir. Aritmetiğin temel teoremine göre bütün bileşik sayılar, asal çarpanların çarpımı olarak yazılabilmektedir.

        /// <summary>
        /// Sayının tüm asal çarpanlarını bulma
        /// </summary>
        static IList<int> PrimeFactors(int n)
        {
            var factors = new List<int>();

            for(var i = 2; i <= Math.Sqrt(n); i++)
            {
                while(n % i == 0)
                {
                    n /= i;
                    factors.Add(i);
                }
            }

            if (n != 1)
                factors.Add(n);

            return factors;
        }