Check Prime Number

Q: Bir sayının asal olup olmadığını kontrol etmenin zaman karmaşıklığı nedir?

√n değerine kadar deneme bölmesi O(√n) zaman ve O(1) alan alır. n değeri 2^31-1 'e kadar olduğunda bu, en fazla yaklaşık 46,000 bölme eder; çift bölenleri atlarsanız 23,000 bölme eder. n-1 'e kadar her böleni denemek O(n) karmaşıklığındadır; en büyük girdi için yaklaşık iki milyar adım gerektirir.

Q: Neden bölenleri yalnızca n'nin kareköküne kadar kontrol ediyorsun?

Bölenler, çarpımları n olan d ve n / d çiftleri hâlinde gelir. Her ikisi de √n değerinden büyük olsaydı, çarpımları n değerinden büyük olurdu. Bu nedenle her çiftin en fazla √n değerinde bir elemanı vardır ve o zamana kadar hiçbir bölen ortaya çıkmazsa n asaldır.

Q: 1 asal sayı mıdır?

Hayır. Bir asal sayının tam olarak iki farklı böleni vardır: 1 ve kendisi; 1 'in ise yalnızca bir böleni vardır. 1 'i dışarıda bırakmak, her tam sayının asal çarpanlarına ayrılışının benzersiz olmasını sağlar. Bu nedenle isPrime(1) , false döndürür.

Q: Çok büyük sayıların asal olup olmadığını test etmenin daha hızlı bir yolu var mı?

Tek bir 32 bitlik sayı için √n 'ye kadar deneme bölmesi yeterince hızlıdır. Onlarca basamaklı sayılar için programlar, bölenleri denemek yerine birkaç modüler kuvveti kontrol eden Miller-Rabin testini kullanır. Bir sınıra kadar tüm asal sayıları listelemek için Eratosthenes Kalburu, her sayıyı tek tek test etmekten daha etkilidir.

BaşlangıçMatematik ve simülasyon

+10

Asal sayı, yalnızca 1 ve kendisine bölünebilen, 1'den büyük bir tam sayıdır. Pozitif bir n tam sayısı veriliyor. n asal ise true, değilse false döndürün. 1 sayısı asal değildir.

Fonksiyon

isPrime(n: integer) → boolean

ninteger: test edilecek pozitif tam sayı
Döndürürboolean: n asal ise true, aksi halde false

Kısıtlar

1 ≤ n ≤ 2³¹ - 1

Örnekler

Girdi: n = 29
Çıktı: true
Açıklama: 2, 3, 4 veya 5 sayılarından hiçbiri 29'u bölmez ve 6 × 6 = 36, 29'u zaten aşar; dolayısıyla bulunacak başka bölen kalmaz. 29 asaldır.

Girdi: n = 1
Çıktı: false
Açıklama: Bir asal sayının tam olarak iki böleni vardır: 1 ve kendisi. 1 yalnızca bir böleni olduğundan, cevap false olur.

Girdi: n = 91
Çıktı: false
Açıklama: 91 asal gibi görünür, ancak 7 × 13 = 91. Arama √91 ≈ 9.5 değerini geçmeden önce 7 böleni bulunur.

Gönderirken +15 gizli test

Ek soru

3'ten büyük her asal sayı 6k-1 veya 6k+1 biçimindedir. Aday bölenlerin yalnızca üçte birini test etmek için bunu kullanabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Tanım, 2 ile n-1 arasındaki her böleni elememizi söyler; en büyük asal girdi için bu, iki milyardan fazla bölme işlemi demektir. Bölenler, çarpımları n olan çiftler hâlinde gelir ve her çiftin küçük olanı en fazla √n değerindedir. Bu yüzden yalnızca √n değerine kadar arama yaparsın; en fazla yaklaşık 23,000 tek aday.

Her böleni dene

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Tanım algoritmayı verir. n ≥ 2 sayısı, 2, 3, ..., n-1 sayılarından hiçbiri onu bölmüyorsa asaldır. Her d adayı için n % d == 0 koşulunu sınayın ve bölen ilk adayda false döndürün. 91 için döngü 2 ile 6 arasındaki sayıları dener ve 7'de durur.

Önce n < 2 durumunu ele alın. n = 1 için aday aralığı boştur; dolayısıyla döngü hiçbir zaman bölen bulamaz ve 1 sayısını asal olarak değerlendirir.

Bileşik sayılar genellikle erken durur, ancak asal sayılar her testten geçer; bu nedenle döngü sonuna kadar çalışır. Asal olan n = 2147483647 için bu, yaklaşık 2.1 × 10^9 bölme demektir; bu da birkaç saniyede yapılabilecek olandan çok daha fazladır.

Algoritma

n < 2 ise false döndür.
d değerini 2'den n-1'e kadar döngüye sok.
n % d == 0 ise false döndür.
Döngüden sonra true döndür.

def isPrime(n):
    if n < 2:
        return False
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

Kareköküne kadar deneme bölmesi

Sezgi

Bölenler çiftler hâlinde gelir. d, n'yi bölüyorsa n / d de böler ve bu iki sayının çarpımı n olur. Çarpımları n'den büyük olacağı için ikisi birden √n'den büyük olamaz. Dolayısıyla n'nin 1 ve kendisi dışında bir böleni varsa, √n'ye eşit veya ondan küçük bir böleni de vardır. 91 için çift 7 ve 13'tür ve 7 ≤ 9.5. √n'ye kadar hiçbir sayı n'yi bölmüyorsa, ondan büyük hiçbir sayı da bölmez.

Karekök işlevi çağırmak yerine sınırı d * d ≤ n olarak yaz. Böylece yuvarlama olmadan tam sayılarla işlem yapılır. Eşitlik işareti önemlidir: 49 = 7 × 7 ve tek böleni olan 7, tam olarak √49 değerindedir.

Adayların yarısını da atlayabilirsin. 2'yi ayrıca ele al: çift bir n yalnızca 2 ise asaldır. Bundan sonra tek bir n'nin yalnızca tek bölenleri olur; bu nedenle 3'ten başla ve 2'şer artır. n = 2147483647 için döngü artık 2.1 × 10^9 yerine yaklaşık 23,000 kez çalışır.

Algoritma

n < 2 ise false döndürün.
n çiftse, n == 2 olup olmadığını döndürün.
d değerini 3 olarak başlatın ve d * d ≤ n olduğu sürece, d için 64 bitlik bir tür kullanarak döngüye devam edin.
n % d == 0 ise false döndürün. Aksi takdirde d değerine 2 ekleyin.
Döngüden sonra true döndürün.

def isPrime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2  # 2 is the only even prime
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

Tuzaklar ve uç durumlar

Fikir tek bir satıra sığar. Hatalar sınırlarda ortaya çıkar: en küçük girdilerde ve son bölen kontrolünde.

1 için true döndürmek. Bir böleni vardır, iki değil; bu yüzden asal değildir.
Çift olduğu için 2 sayısını reddetmek. Çift sayıları elemeden önce n == 2 kontrolünü yapın.
≤ yerine d * d < n koşulu sağlandığı sürece döngüye devam etmek. Böylece 9, 49 ve 2147117569 = 46337² gibi asal sayıların kareleri asal olarak kabul edilir.
d * d işleminde taşma. 32 bitlik bir int türünde 46341 × 46341 = 2147488281 sığmaz ve negatif bir sayıya dönüşerek taşar; bu nedenle kontrol sürekli başarılı olur ve döngü √n değerinin çok ötesine kadar devam eder. d için 64 bitlik bir tür kullanın veya bunun yerine d ≤ n / d koşulunu karşılaştırın.
Sınırı kayan noktalı sqrt sonucundan alıp kesmek. Buradaki tüm n değerleri için bir double kesin sonuç verir; ancak 64 bitlik girdilerde yuvarlama, gerçek karekökün bir altındaki değere denk gelebilir ve önemli olan tek bölenin atlanmasına neden olabilir. d * d ≤ n böyle bir risk taşımaz.

Sıkça sorulan sorular4

Bir sayının asal olup olmadığını kontrol etmenin zaman karmaşıklığı nedir?

√n değerine kadar deneme bölmesi O(√n) zaman ve O(1) alan alır. n değeri 2^31-1'e kadar olduğunda bu, en fazla yaklaşık 46,000 bölme eder; çift bölenleri atlarsanız 23,000 bölme eder. n-1'e kadar her böleni denemek O(n) karmaşıklığındadır; en büyük girdi için yaklaşık iki milyar adım gerektirir.

Neden bölenleri yalnızca n'nin kareköküne kadar kontrol ediyorsun?

Bölenler, çarpımları n olan d ve n / d çiftleri hâlinde gelir. Her ikisi de √n değerinden büyük olsaydı, çarpımları n değerinden büyük olurdu. Bu nedenle her çiftin en fazla √n değerinde bir elemanı vardır ve o zamana kadar hiçbir bölen ortaya çıkmazsa n asaldır.

1 asal sayı mıdır?

Hayır. Bir asal sayının tam olarak iki farklı böleni vardır: 1 ve kendisi; 1'in ise yalnızca bir böleni vardır. 1'i dışarıda bırakmak, her tam sayının asal çarpanlarına ayrılışının benzersiz olmasını sağlar. Bu nedenle isPrime(1), false döndürür.

Çok büyük sayıların asal olup olmadığını test etmenin daha hızlı bir yolu var mı?

Tek bir 32 bitlik sayı için √n'ye kadar deneme bölmesi yeterince hızlıdır. Onlarca basamaklı sayılar için programlar, bölenleri denemek yerine birkaç modüler kuvveti kontrol eden Miller-Rabin testini kullanır. Bir sınıra kadar tüm asal sayıları listelemek için Eratosthenes Kalburu, her sayıyı tek tek test etmekten daha etkilidir.

Python

def isPrime(n):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

n = 29

Beklenen

true