Asal Sayı Denetleyici ve Çarpanlara Ayırıcı

Nasıl kullanılır

1. Bir mod seçin: tek bir sayıyı denetleyin, çarpanlarına ayırın, N'ye kadarki asalları listeleyin ya da komşu asalları bulun.
2. Sayıyı yazın — binlik ayıracı olarak kullanılan noktalar kabul edilir ve yok sayılır.
3. Sonuç, onu üreten bölmelerle birlikte görünür. Her şey tarayıcınızda hesaplanır.

Bu araç hakkında

Bir asal sayının tam olarak iki böleni vardır: 1 ve kendisi. Bu, asalları aritmetiğin yapı taşı yapar: 1'den büyük her tam sayı, asalların çarpımı olarak tam olarak tek bir şekilde yazılır; aritmetiğin temel teoremi bunu söyler. 360 sayısı 2³ × 3² × 5'tir, başka bir şey değil; 91 asal gibi görünür ama aslında 7 × 13'tür; 97 ise gerçekten asaldır. Çarpanlara ayrılış bilindiğinde başka bilgiler bedavaya gelir — bölen sayısı, her üsse bir eklenip çarpılarak bulunur; yani 360 sayısının (3 + 1) × (2 + 1) × (1 + 1) = 24 böleni vardır.

Buradaki asallık denetimi deneme bölmesiyle yapılır, ama yalnızca sayının kareköküne kadar ve yalnızca 6k ± 1 biçimindeki adaylara karşı; çünkü geri kalan her şey zaten 2'nin ya da 3'ün katıdır. Bu, işin üçte ikisini atlar ve bir trilyonun altındaki bir sayıyı birkaç yüz bin bölmeyle, yani birkaç milisaniyede sonuca bağlar. 10¹² üzerinde bu bile tarayıcıda yavaşlar; bu yüzden yanıt, 2'den 37'ye kadarki tabanlarla deterministik Miller-Rabin testine geçer. Bu test 3,3×10²⁴ altındaki her sayı için, dolayısıyla bu aracın kabul ettiği 2⁵³ − 1'e kadarki her şey için kanıtlanmış biçimde kesindir. Asalları listelemek başka bir klasiği kullanır: Eratosthenes kalburu N'ye kadarki her sayıyı yazar, işaretlenmemiş en küçüğünü tutar, onun tüm katlarını çizer ve yalnızca asallar kalana dek tekrarlar.

Asal çarpanlara ayırma; kesir sadeleştirmenin, EKOK ya da EBOB bulmanın ve karekökleri sadeleştirmenin arkasındaki mekanizmadır — bu yüzden erken öğretilir. Okulun ötesinde, büyük sayıları çarpanlarına ayırmanın zorluğu RSA şifrelemesinin dayandığı temeldir: iki büyük asalı çarpmak anlıktır, bunu geri almak değildir ve aradaki fark bütün güvenlik gerekçesidir. Asallar sayılar büyüdükçe öngörülebilir biçimde seyrekleşir ama asla tükenmez — Öklid bunu iki bin yıldan uzun süre önce kanıtladı. Burada 2⁵³ − 1'e kadarki sayılar denetlenebilir; çarpanlara ayırma ve komşu asallar bir trilyona kadar, asal listesi ise 100.000'e kadar çalışır. Yazdığınız hiçbir şey tarayıcınızdan çıkmaz.

Formül

Deneme bölmesiyle asallık: 2'den √n değerine kadar hiçbir tam sayı n sayısını tam bölmüyorsa n asaldır ve 2, 3 ile ardından 6k ± 1 biçimindeki her adayı denemek yeterlidir. Çarpanlara ayırma aynı bölmeleri uygular ve her asalın kaç kez sığdığını kaydeder; bölen sayısı, her üsse bir eklenip çarpılarak bulunur. Asal listesi Eratosthenes kalburunu kullanır. 10^12 üzerinde asallık yanıtı, 2'den 37'ye tabanlarla deterministik Miller-Rabin testinden gelir; bu test 2^53 altındaki her sayı için kesindir.

Sık sorulan sorular