6XC

Asal Sayı Listesi ve Testi

Bir aralıktaki tüm asal sayıları listeleyin (Eratosthenes Kalburu) veya tek bir sayının asal olup olmadığını kontrol edin — anında sonuç.

1.054 görüntülenme

Nasıl Çalışır

Araç, farklı iki soruya cevap veren iki ayrı algoritma arasında geçiş yapar. Liste modu, belirli bir sınıra kadar tüm asalları Eratosthenes Kalburu ile bulur — hâlâ günlük kullanılan en eski algoritmalardan biri (MÖ 3. yüzyılda yaşamış Yunan matematikçi Eratosthenes'e atfedilir). 2'den başlanır, 2'nin tüm katları elenir (bileşik işaretlenir), ardından işaretlenmemiş bir sonraki sayıya (3) geçilip onun katları elenir, sonra 5'e geçilir, ve böyle devam eder. Sınırın kareköküne ulaşıldığında işaretlenmeden kalan her sayı asaldır. Küçük bir örnek: 30'a kadar kalburlamak için önce 2'nin katlarını (4,6,8,…), sonra 3'ün katlarını (6,9,12,…, bir kısmı zaten elenmiş), sonra 5'in katlarını (10,15,…) eleyin — 5×5=25 ≤ 30 ama 7×7=49 > 30 olduğundan burada durabilirsiniz; geriye kalanlar — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — tam listedir. Bu işlem O(n log log n) karmaşıklığıyla çalışır, yani aralık yüz binlere çıksa bile hızını korur.

Test modu farklı bir soruya cevap verir — bu belirli sayı asal mı? — ve bunun için √n'e kadar deneme bölmesi kullanır. n'in asal olup olmadığını test etmek için 2'den √n'e kadar bölenleri kontrol etmek yeterlidir. Mantık şöyle: eğer n = a × b ise ve hem a hem b √n'den büyükse, a × b çarpımı n'den büyük olurdu ki bu imkânsızdır. Yani iki çarpandan en az biri √n veya daha küçük olmak zorundadır ve döngü bitmeden bulunur. Örnek: 97'yi test etmek için yalnızca 2, 3, 5, 7'ye bölünüp bölünmediğine bakmak yeterlidir (çünkü 9²=81 ≤ 97 ama 10²=100 > 97) — hiçbiri tam bölmez, dolayısıyla 97 asaldır.

Bilinmesi Gerekenler

İki modun var olmasının nedeni farklı ödünleşimler sunmalarıdır: kalbur, aynı anda birçok asal üretmek için verimlidir ama dev bir sınıra yakın tek bir sayıyla ilgileniyorsanız zaman ve bellek israf eder; deneme bölmesi tek bir kontrol için verimlidir ama geniş bir aralıktaki her sayı için tek tek tekrarlanırsa çok yavaş kalır. Doğru olanı işe göre seçmek, bu aracın ikisini birden sunmasının tam nedenidir.

  • 1, tanım ve gelenek gereği asallardan hariç tutulur — yalnızca bir böleni vardır, iki değil; dahil edilseydi asal çarpanlara ayırmanın tekliğini bozardı.
  • 2, tek çift asal sayıdır; diğer tüm çift sayılar 2'ye bölünebildiği için bileşiktir.
  • Sayılar büyüdükçe asallar ortalama olarak seyrekleşir, ama hiçbir zaman tükenmez — Euklid, iki bin yıldan uzun süre önce sonsuz sayıda asal olduğunu kanıtlamıştır.

Sıkça Sorulan Sorular

Asal sayı ne demektir?

1'den büyük, tam olarak iki pozitif böleni olan doğal sayıdır: 1 ve kendisi. 1 asal değildir çünkü tek böleni vardır; negatif sayılar ise asal ya da bileşik sayılmaz.

En fazla ne kadar geniş bir aralık listeleyebilirim?

1.000.000'a kadar — bu aralıkta Eratosthenes Kalburu hızını korur (O(n log log n) karmaşıklığı çok yavaş büyür) ve tarayıcınız yanıt vermeye devam eder.

Deneme bölmesi neden yalnızca kareköke kadar kontrol eder?

Eğer n sayısının √n'den büyük bir böleni varsa, bu bölen mutlaka √n'den küçük bir bölenle eşleşir (çarpımları n'e eşit olduğundan). Yani her çarpan çiftinin en az bir üyesi kareköke eşit veya ondan küçüktür — daha ileri kontrol gereksizdir.

Neden listeleme için de deneme bölmesi kullanılmıyor?

Kullanılabilirdi ama çok daha yavaş olurdu: aralıktaki her sayıyı tek tek kendi karekökeüne kadar test etmek, kalburun yaptığından çok daha fazla tekrar iş gerektirir — kalbur, her asalın katlarını tüm aralık boyunca tek bir verimli geçişte eler.

Sonsuz sayıda asal var mıdır?

Evet — Euklid, MÖ 300 civarında şu kanıtı vermiştir: tüm asalların sonlu bir listesi olduğunu varsayın, hepsini çarpıp 1 ekleyin; sonuç, listedeki hiçbir asala tam bölünmez, dolayısıyla ya kendisi yeni bir asaldır ya da listede olmayan bir asal çarpanı vardır. Her iki durumda da liste eksik kalmıştır.

Yorumlar

Henüz yorum yok — ilk yorumu siz yazın!

Benzer Araçlar

Hesap Makinesi Klavye destekli ücretsiz online hesap makinesi: dört işlem, yüzde, parantez ve işlem geçmişi. Çalıştır Yüzde Hesaplama Bir sayının yüzdesini, bir sayının başka bir sayıya oranını ve yüzde artış-azalışı (zam, indirim) hesaplayın. Hesapla EBOB EKOK Hesaplama İki veya daha fazla sayının EBOB'unu (en büyük ortak bölen) ve EKOK'unu (en küçük ortak kat) anında hesaplayın. Hesapla Kombinasyon ve Permütasyon Hesaplama C(n,r) kombinasyon, P(n,r) permütasyon ve n! faktöriyel değerlerini tam sonuçla hesaplayın. Hesapla