Paylaşım Yap
Tüm Reklamları Kapat
Tüm Reklamları Kapat

Project Euler 3: En Büyük Asal Çarpan

Project Euler 3: En Büyük Asal Çarpan
3 dakika
850
  • Özgün
Tüm Reklamları Kapat
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ı

Project Euler 2 çözümünde kullanılabilecek bir asal sayı algoritması olan Eratosthenes'in eleği algoritması
Project Euler 2 çözümünde kullanılabilecek bir asal sayı algoritması olan 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ı
Bu Makaleyi Alıntıla
Okundu Olarak İşaretle
0
Paylaş
Sonra Oku
Notlarım
Yazdır / PDF Olarak Kaydet
Bize Ulaş
Yukarı Zıpla

İç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
Bu İçerik Size Ne Hissettirdi?
  • Muhteşem! 0
  • Tebrikler! 0
  • Bilim Budur! 0
  • Mmm... Çok sapyoseksüel! 0
  • Güldürdü 0
  • İnanılmaz 0
  • Umut Verici! 0
  • Merak Uyandırıcı! 0
  • Üzücü! 0
  • Grrr... *@$# 0
  • İğrenç! 0
  • Korkutucu! 0
Tüm Reklamları Kapat

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 21/02/2024 10:46:22 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.

Tüm Reklamları Kapat
Keşfet
Akış
İçerikler
Gündem
Kas
Balıklar
Endokrin Sistemi Hastalıkları
Çalışma
Argüman
Diş Gelişimi
Konuşma
Kuyruksuz Maymun
Hormon
Patojen
Böcek
Mitler
Mikrobiyoloji
Mars
Lazer
Akademi
Kromozom
Dilbilim
Onkoloji
Tümör
Genetik Mühendisliği
Karanlık Madde
Kırmızı
Yüz
Besin Değeri
Aklımdan Geçen
Komünite Seç
Aklımdan Geçen
Fark Ettim ki...
Bugün Öğrendim ki...
İşe Yarar İpucu
Bilim Haberleri
Hikaye Fikri
Video Konu Önerisi
Başlık
Gündem
Bugün bilimseverlerle ne paylaşmak istersin?
Bağlantı
Kurallar
Komünite Kuralları
Bu komünite, aklınızdan geçen düşünceleri Evrim Ağacı ailesiyle paylaşabilmeniz içindir. Yapacağınız paylaşımlar Evrim Ağacı'nın kurallarına tabidir. Ayrıca bu komünitenin ek kurallarına da uymanız gerekmektedir.
1
Bilim kimliğinizi önceleyin.
Evrim Ağacı bir bilim platformudur. Dolayısıyla aklınızdan geçen her şeyden ziyade, bilim veya yaşamla ilgili olabilecek düşüncelerinizle ilgileniyoruz.
2
Propaganda ve baskı amaçlı kullanmayın.
Herkesin aklından her şey geçebilir; fakat bu platformun amacı, insanların belli ideolojiler için propaganda yapmaları veya başkaları üzerinde baskı kurma amacıyla geliştirilmemiştir. Paylaştığınız fikirlerin değer kattığından emin olun.
3
Gerilim yaratmayın.
Gerilim, tersleme, tahrik, taciz, alay, dedikodu, trollük, vurdumduymazlık, duyarsızlık, ırkçılık, bağnazlık, nefret söylemi, azınlıklara saldırı, fanatizm, holiganlık, sloganlar yasaktır.
4
Değer katın; hassas konulardan ve öznel yoruma açık alanlardan uzak durun.
Bu komünitenin amacı okurlara hayatla ilgili keyifli farkındalıklar yaşatabilmektir. Din, politika, spor, aktüel konular gibi anlık tepkilere neden olabilecek konulardaki tespitlerden kaçının. Ayrıca aklınızdan geçenlerin Türkiye’deki bilim komünitesine değer katması beklenmektedir.
5
Cevap hakkı doğurmayın.
Bu platformda cevap veya yorum sistemi bulunmamaktadır. Dolayısıyla aklınızdan geçenlerin, tespit edilebilir kişilere cevap hakkı doğurmadığından emin olun.
Ekle
Soru Sor
Sosyal
Yeniler
Daha Fazla İçerik Göster
Evrim Ağacı'na Destek Ol
Evrim Ağacı'nın %100 okur destekli bir bilim platformu olduğunu biliyor muydunuz? Evrim Ağacı'nın maddi destekçileri arasına katılarak Türkiye'de bilimin yayılmasına güç katmak için hemen buraya tıklayın.
Popüler Yazılar
30 gün
90 gün
1 yıl
EA Akademi
Evrim Ağacı Akademi (ya da kısaca EA Akademi), 2010 yılından beri ürettiğimiz makalelerden oluşan ve kendi kendinizi bilimin çeşitli dallarında eğitebileceğiniz bir çevirim içi eğitim girişimi! Evrim Ağacı Akademi'yi buraya tıklayarak görebilirsiniz. Daha fazla bilgi için buraya tıklayın.
Etkinlik & İlan
Bilim ile ilgili bir etkinlik mi düzenliyorsunuz? Yoksa bilim insanlarını veya bilimseverleri ilgilendiren bir iş, staj, çalıştay, makale çağrısı vb. bir duyurunuz mu var? Etkinlik & İlan Platformumuzda paylaşın, milyonlarca bilimsevere ulaşsın.
Youtube
Yeni Yapay Zeka
Yeni Yapay Zeka "Sora", YouTube'un Sonu Olabilir mi?
Filler Neden Farelerden Korkar?
Filler Neden Farelerden Korkar?
Büyünün Çalışıp Çalışmadığını Nasıl Anlarsınız?
Büyünün Çalışıp Çalışmadığını Nasıl Anlarsınız?
Yıldırım Topu: Bulutlardan Gelen Gizemli Elektrik Topu!
Yıldırım Topu: Bulutlardan Gelen Gizemli Elektrik Topu!
Arabada/Gemide Neden Mideniz Bulanıyor (Araç Tutuyor)?
Arabada/Gemide Neden Mideniz Bulanıyor (Araç Tutuyor)?
Podcast
Evrim Ağacı'nın birçok içeriğinin profesyonel ses sanatçıları tarafından seslendirildiğini biliyor muydunuz? Bunların hepsini Podcast Platformumuzda dinleyebilirsiniz. Ayrıca Spotify, iTunes, Google Podcast ve YouTube bağlantılarını da bir arada bulabilirsiniz.
Yazı Geçmişi
Okuma Geçmişi
Notlarım
İlerleme Durumunu Güncelle
Okudum
Sonra Oku
Not Ekle
Kaldığım Yeri İşaretle
Göz Attım

Evrim Ağacı tarafından otomatik olarak takip edilen işlemleri istediğin zaman durdurabilirsin.
[Site ayalarına git...]

Filtrele
Listele
Bu yazıdaki hareketlerin
Devamını Göster
Filtrele
Listele
Tüm Okuma Geçmişin
Devamını Göster
0/10000
Bu Makaleyi Alıntıla
Evrim Ağacı Formatı
APA7
MLA9
Chicago
Ö. Kayalı. Project Euler 3: En Büyük Asal Çarpan. (30 Aralık 2019). Alındığı Tarih: 21 Şubat 2024. Alındığı Yer: https://evrimagaci.org/s/12647
Kayalı, Ö. (2019, December 30). Project Euler 3: En Büyük Asal Çarpan. Evrim Ağacı. Retrieved February 21, 2024. from https://evrimagaci.org/s/12647
Ö. Kayalı. “Project Euler 3: En Büyük Asal Çarpan.” Edited by Ögetay Kayalı. Evrim Ağacı, 30 Dec. 2019, https://evrimagaci.org/s/12647.
Kayalı, Ögetay. “Project Euler 3: En Büyük Asal Çarpan.” Edited by Ögetay Kayalı. Evrim Ağacı, December 30, 2019. https://evrimagaci.org/s/12647.
ve seni takip ediyor
Evrim Ağacı Uygulamasını
İndir
Chromium Tabanlı Mobil Tarayıcılar (Chrome, Edge, Brave vb.)
İlk birkaç girişinizde zaten tarayıcınız size uygulamamızı indirmeyi önerecek. Önerideki tuşa tıklayarak uygulamamızı kurabilirsiniz. Bu öneriyi, yukarıdaki videoda görebilirsiniz. Eğer bu öneri artık gözükmüyorsa, Ayarlar/Seçenekler (⋮) ikonuna tıklayıp, Uygulamayı Yükle seçeneğini kullanabilirsiniz.
Chromium Tabanlı Masaüstü Tarayıcılar (Chrome, Edge, Brave vb.)
Yeni uygulamamızı kurmak için tarayıcı çubuğundaki kurulum tuşuna tıklayın. "Yükle" (Install) tuşuna basarak kurulumu tamamlayın. Dilerseniz, Evrim Ağacı İleri Web Uygulaması'nı görev çubuğunuza sabitleyin. Uygulama logosuna sağ tıklayıp, "Görev Çubuğuna Sabitle" seçeneğine tıklayabilirsiniz. Eğer bu seçenek gözükmüyorsa, tarayıcının Ayarlar/Seçenekler (⋮) ikonuna tıklayıp, Uygulamayı Yükle seçeneğini kullanabilirsiniz.
Safari Mobil Uygulama
Sırasıyla Paylaş -> Ana Ekrana Ekle -> Ekle tuşlarına basarak yeni mobil uygulamamızı kurabilirsiniz. Bu basamakları görmek için yukarıdaki videoyu izleyebilirsiniz.

Daha fazla bilgi almak için tıklayın

Göster

Şifrenizi mi unuttunuz? Lütfen e-posta adresinizi giriniz. E-posta adresinize şifrenizi sıfırlamak için bir bağlantı gönderilecektir.

Geri dön

Eğer aktivasyon kodunu almadıysanız lütfen e-posta adresinizi giriniz. Üyeliğinizi aktive etmek için e-posta adresinize bir bağlantı gönderilecektir.

Geri dön

Close