Project Euler 3: En Büyük Asal Çarpan
Project Euler 3: 13195 sayısının asal çarpanları 5, 7, 13 ve 29'dur. 600851475143 sayının en büyük asal çarpanı nedir?Project Euler 3 sorusunda karşımıza yine bir algoritma klasiği çıkıyor: Asal sayılar.
Asal sayıları elde edebileceğimiz bir sürü algoritma mevcut. Bunları incelemenizi şiddetle tavsiye ediyorum. Bir sayının asal sayı olup olmadığını denetlemenin en kaba yolu o sayıyı kendisine kadar olan sayma sayılarına bölmektir. Bu sayı bir ve kendisi hariç başka bir sayıya bölünmüyorsa asal bir sayıdır.
Fakat bu yöntem fazlasıyla gereksiz işlem kalabalığına sahiptir. Örneğin hiçbir asal sayı çift değildir, çünkü çift her sayı ikinin bir katıdır. Bu yüzden her seferinde çift sayıları kontrol etmek anlamsızdır (takdir edersiniz ki bu iki kat fazla sayının kontrol edilmesi demek). Bu soruda biz de tam olarak bu mantıktan ilerleyen bir algoritmayı ele alacağız. Lakin belirtmek isterim ki, algoritma dünyasında hızlı bir şekilde asal sayı bulmak oldukça önemli bir yere sahiptir ve bu bahsedeceğimiz algoritmalardan daha hızlıları da mevcuttur.
Eratosthenes'in Eleği Algoritması
Bu algoritma 2'den başlayarak eleme yöntemiyle asal sayıların belirlenmesini sağlar. Öncelikle ilk sayı olan 2 asal olarak yazılır ve eldeki listeden 2'nin katları silinir. Sonra sıradaki sayı olan 3'e geçilir ve 3'ün katları silinir. Sıradaki sayı 4 değildir, çünkü 2'nin katı olduğundan elenmiştir. Dolayısıyla sıradaki sayı 5'tir, asal olarak yazılır ve katları silinir. İşlem bu şekilde devam eder. Liste sona erdiğinde, geriye kalan sayılar yalnızca asal sayılardır.Kareköke Kadar İncelemek
Denetlemeyi sayının kareköküne kadar olan sayılara kadar yapmak yeterlidir. Örneğin 100 sayısının asal olup olmadığını denetlemek için karekök 100'e yani 10'a kadar olan sayılara bakmak yeterlidir (bu yöntemin bizi ne kadar işlem kalabalığından kurtardığına dikkat edin). Bunun nedenini düşünmeyi size bırakıyoruz, işin arkasında oldukça şahane bir düşünce yatıyor. Eminiz elinize bir kağıt kalem alıp yazmaya başlayarak bunu kendiniz de görebilirsiniz.C# Çözümü
Eğer sayıları bir dizide kabul eder ve dizinin asal olmayan elemanlarına yanlış değerini atarsak, dizinin doğru olan elemanlarının numarası bize asal sayıları verir. Böylece kodumuz aşağıdaki şekilde olur.Şimdi yapmamız gereken işlem, bize verilen sayı olan 600851475143'ün karaköküne kadar olan asal sayıları Eratosthenes'in Eleği yöntemini kullanarak oluşturmak. Ardından sayımızı bu asal sayılara bölerek, hangisinin en büyük asal çarpan olacağını bulabiliriz.
Sonuç: 71, 839, 1471, 6857 olarak bulunur.
Python Çözümü
Belirli bir n değerine kadar olan asal sayıları liste haline getiren fonksiyon:Ardından hesabımızın yapıldığı kod parçası:
Çıktı:
Neredeyse saniyenin 10'da 1'i gibi bir sürede çözüldüğünü görebiliyoruz. Elbette ilerleyen problemlerde artan işlem kalabalığı nedeniyle bu bir problem teşkil etmeye başlayacak. O nedenle şimdiden, kodunuzu mümkün olan en yüksek hıza çıkartacak optimizasyonlara kafa yormanızı öneririm.
Eğer daha hızlı bir asal sayı bulma algoritması kullanırsak (ayrıca bkz.):
Sürenin 3.5 kat kadar (%350) daha hızlandığını görüyoruz ki bu muhteşem bir gelişme. Ayrıca dikkatinizi çekmek istediğim bir nokta da asal çarpanları bulurken yaptığımız hamledir. Bize en büyük asal çarpan sorulduğundan ötürü listede küçük asallardan değil, büyük asallardan başlayarak taradık. Böylece daha az deneme yapmış olduk.
Ögetay Kayalı
İçeriklerimizin bilimsel gerçekleri doğru bir şekilde yansıtması için en üst düzey çabayı gösteriyoruz. Gözünüze doğru gelmeyen bir şey varsa, mümkünse güvenilir kaynaklarınızla birlikte bize ulaşın!
Bu içeriğimizle ilgili bir sorunuz mu var? Buraya tıklayarak sorabilirsiniz.
Soru & Cevap Platformuna Git- 0
- 0
- 0
- 0
- 0
- 0
- 0
- 0
- 0
- 0
- 0
- 0
Evrim Ağacı'na her ay sadece 1 kahve ısmarlayarak destek olmak ister misiniz?
Şu iki siteden birini kullanarak şimdi destek olabilirsiniz:
kreosus.com/evrimagaci | patreon.com/evrimagaci
Çıktı Bilgisi: Bu sayfa, Evrim Ağacı yazdırma aracı kullanılarak 19/03/2024 15:35:48 tarihinde oluşturulmuştur. Evrim Ağacı'ndaki içeriklerin tamamı, birden fazla editör tarafından, durmaksızın elden geçirilmekte, güncellenmekte ve geliştirilmektedir. Dolayısıyla bu çıktının alındığı tarihten sonra yapılan güncellemeleri görmek ve bu içeriğin en güncel halini okumak için lütfen şu adrese gidiniz: https://evrimagaci.org/s/12647
İçerik Kullanım İzinleri: Evrim Ağacı'ndaki yazılı içerikler orijinallerine hiçbir şekilde dokunulmadığı müddetçe izin alınmaksızın paylaşılabilir, kopyalanabilir, yapıştırılabilir, çoğaltılabilir, basılabilir, dağıtılabilir, yayılabilir, alıntılanabilir. Ancak bu içeriklerin hiçbiri izin alınmaksızın değiştirilemez ve değiştirilmiş halleri Evrim Ağacı'na aitmiş gibi sunulamaz. Benzer şekilde, içeriklerin hiçbiri, söz konusu içeriğin açıkça belirtilmiş yazarlarından ve Evrim Ağacı'ndan başkasına aitmiş gibi sunulamaz. Bu sayfa izin alınmaksızın düzenlenemez, Evrim Ağacı logosu, yazar/editör bilgileri ve içeriğin diğer kısımları izin alınmaksızın değiştirilemez veya kaldırılamaz.