Eratosthenes kalburu hakkında - en eski asal sayı kalburu
Eratosthenes kalburu, bir sınıra kadar tüm asal sayıları tek bir bölme yapmadan bulur. Sadece sayarsınız: 2'den sonra her ikinci sayıyı, 3'ten sonra her üçüncü sayıyı silin ve böyle devam edin. Geriye kalanlar asal sayılardır. İki bin yıldan fazla bir süre sonra bile onları listelemenin en hızlı yollarından biridir.
Kireneli Eratosthenes
Eratosthenes yaklaşık MÖ 276 ile 194 arasında yaşadı ve büyük İskenderiye Kütüphanesi'nin başındaydı. En çok, iki şehirdeki gölgelerin uzunluğundan Dünya'nın büyüklüğünü ölçmesiyle tanınır. Kalbur onun adını taşır, çünkü Geraseli Nikomakhos onu MS 100 civarında yazdığı Aritmetiğe Giriş'te onun yöntemi olarak anlatmıştır.
Kalbur nasıl çalışır
2'den N'ye kadar sayıları yazın. İlk sayı olan 2 asaldır: 4, 6, 8'i ve 2'nin diğer tüm katlarını silin. Kalan bir sonraki sayı olan 3 asaldır: 9, 12, 15'i ve devamını silin. 5, 7 ve kalan sonraki sayılarla devam edin. Hiç silinmeyen bir sayının daha küçük bir çarpanı yoktur, yani asaldır.
Karekökte durun
N'ye kadar her bileşik sayının, N'nin karekökünden büyük olmayan bir asal çarpanı vardır. Yani p², N'yi geçer geçmez silinecek bir şey kalmaz. 100'e kadar asallar için yalnızca 2, 3, 5 ve 7 yeterlidir, 1000 için ise 31'e kadar olan asallar gerekir.
Ne kadar hızlıdır?
Kalbur yaklaşık N log log N adım sürer, bu da N'nin kendisinden yalnızca biraz daha hızlı büyür. Bilgisayarlar onu hâlâ, çoğu zaman parçalar hâlinde bölümlenmiş kalbur olarak, milyarlara kadar asalları listelemek için kullanır. Tek bir büyük sayının asal olup olmadığını sınamak için başka yöntemler daha hızlıdır.
Sık sorulan sorular
Eratosthenes kalburunu kim icat etti?
Adını MÖ 3. yüzyılda yaşamış Yunan bilgin Kireneli Eratosthenes'ten alır. Bilinen en eski yazılı anlatım, MS 100 civarında Geraseli Nikomakhos'a aittir.
Kalbur neden silmeye p²'den başlar?
p'nin her küçük katının daha küçük bir asal çarpanı vardır, yani daha küçük bir asal onu zaten silmiştir.
1000'in altında kaç asal sayı vardır?
1000'in altında 168 asal sayı vardır. En büyüğü 997'dir.
İlgili araçlar
Eratosthenes kalburu
Eratosthenes kalburunun 100, 200, 500 veya 1000'e kadar asal sayıları nasıl bulduğunu izleyin. Her asal sayı katlarını kendi renginde adım adım siler.
Ulam sarmalı
Ulam sarmalını tarayıcınızda çizin. Asalları işaretleyin, her köşegendeki ikinci dereceden polinomu okuyun ve Euler’in kesintisiz 40 asallık dizisini açın.
Ulam sarmalı
Stanisław Ulam’ın 1963 sarmalının tam sayıları kare bir ızgaraya nasıl dizdiği, asalların neden ikinci dereceden köşegenlerde toplandığı ve sarmal 41’den başladığında Euler’in kırk asalının nerede durduğu.
Collatz sanısı
Collatz 3n+1 problemini tarayıcınızda keşfedin. Dolu dizilerini izleyin, geometrik bir Collatz ağacı büyütün ve sürekli Collatz fraktalına yakınlaşın.
Bunu denemeye hazır mısın?
Pencere PictorX tarayıcınızda - yükleme yok, başlamak için gerekli kredi kartı yok.
Eratosthenes kalburunu deneyin