altay9
commented
3 years ago Teşekkürler Erdem. Konuştuğumuz üzere, Eratosten kalburuna dayanan algoritmayı şu şekilde ekledim. Bu issue açık kalırsa daha iyi olur. Başkaları da faydalanır. https://github.com/altayhunoglu/algorithms/commit/d6220c9afb5b0a24edf5a4f46c8301922c6ce474
https://github.com/ErdemT09/Count-Primes Daha yavaş olan çözüm yöntemi: Bunu çözmek için aklıma gelen yöntem, n'e kadar olan asal sayılar için bir liste tutup, her sayıyı teker teker bu listenin içindeki yarısından küçük olan asal sayılarla karşıolaştırmaktı. Örneğin 97'yi, 43'e kadar tüm asal sayılarla karşılaştırıp (i % primes.get(j) == 0 şeklinde bir boolean'ı kontrol ederek) ona göre asal olup olmadığını seçmekti. Aslında yarısına kadar da değil, sayının kareköküne kadar kontrol edilmeli. Bu algoritma ise her türlü yavaş bir şey. Karşılaştırma olarak bunu da ekledim (countPrimesSlow method'u).
Hızlı yöntem: "Eratosten kalburu" adlı algoritma kullanılıyor. Başlangıçta 2'den n'e kadar olan tüm tam sayılara bir boolean array asal diyoruz, arrayin tüm üyelerine true diyoruz. 2 sayısı örneğin başlangıçtaki asal sayı. O zaman biz 2'den n'e kadar 2 sayısına 2 ekleyerek yineleyerek bunlara eşleşen arraydaki sayıları false yapıyoruz. Böylece 2'nin katı olan sayıları asallıktan çıkarıyoruz. Arrayde aynı şeyi 3'ün, (4'ün asal olmadığını 2'ye bakarken çıkardık) 5'in katlarını false'a eşitliyoruz. Bu işlemi n-1'in kareköküne kadar tekrarlıyoruz, çünkü örneğin 121 gibi bir sayı 11*17 gibi sayıdan küçük olamaz. 11'den küçük olan asal sayılarla kalan asallar dışında asal olmadığını gösteremeyeceğimiz sayı yok. En sonunda sayılar array'inde true kalan öğelerin sayısını döndürüyoruz. Bu yöntemi da submit ettim.