Perfect Number

Q: Mükemmel bir sayıyı kontrol etmenin zaman karmaşıklığı nedir?

√n 'ye kadar bölen çiftlerini toplamak O(√n) zaman ve O(1) alan alır. n = 10^8 için bu yaklaşık 10^4 adımdır. n / 2 'ye kadar her adayı test etmek O(n) zaman alır; aynı girdi için yaklaşık 5 × 10^7 adımdır.

Q: 10^8'den küçük kaç mükemmel sayı vardır?

Beş tane: 6 , 28 , 496 , 8128 ve 33550336 . Sayıları hızla seyrekleşir. Bir sonraki sayı olan 8589869056 , 32 bitlik bir tam sayıya bile sığmaz.

Q: Tek sayılı mükemmel sayılar var mı?

Kimse bilmiyor. Şimdiye kadar bulunan her mükemmel sayı çifttir. Araştırmalar, 10^1500 değerinin altındaki tek mükemmel sayıları elemiştir, ancak bunların var olamayacağını söyleyen bir kanıt yoktur. Fonksiyonunuz, girdinin çift olduğu tahminine değil, tanıma göre çalışmalıdır.

Q: Mükemmel, bol ve eksik sayılar arasındaki fark nedir?

Uygun bölenlerin toplamını sayıyla karşılaştır. Eşitse mükemmeldir; 28 gibi. Daha büyükse bol sayıdır; bölenlerinin toplamı 16 olan 12 gibi. Daha küçükse eksiktir; tek uygun böleni 1 olan her asal sayı gibi.

BaşlangıçMatematik ve simülasyon

+10

n'nin öz böleni, n'nin kendisinden küçük pozitif bir bölenidir. Mükemmel sayı, öz bölenlerinin toplamına eşittir: 6 = 1 + 2 + 3. Pozitif bir tam sayı olan n veriliyor. n mükemmelse true, değilse false döndürün.

Fonksiyon

isPerfect(n: integer) → boolean

ninteger: test edilecek pozitif tam sayı
Döndürürboolean: n, kendisi dışındaki pozitif bölenlerinin toplamına eşitse true, aksi takdirde false

Kısıtlar

1 ≤ n ≤ 10⁸

Örnekler

Girdi: n = 28
Çıktı: true
Açıklama: 28 sayısının kendisi dışındaki pozitif bölenleri 1, 2, 4, 7 ve 14'tür. Bunların toplamı 28 olduğundan, 28 mükemmeldir.

Girdi: n = 12
Çıktı: false
Açıklama: 12 sayısının kendisi dışındaki pozitif bölenleri 1, 2, 3, 4 ve 6'dır. Bunların toplamı 16 eder; bu da 12'yi aşar.

Girdi: n = 1
Çıktı: false
Açıklama: 1 sayısının hiçbir gerçek böleni yoktur, bu yüzden toplam 1 değil, 0'dır.

Gönderirken +16 gizli test

Ek soru

Her çift mükemmel sayı, 2^(p-1) × (2^p-1) biçimindedir; burada 2^p-1 asaldır. Her sayıyı tek tek test etmeden bu formülle 10^8'den küçük tüm mükemmel sayıları listeleyebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Tanım bölenlerin toplamını istiyor ve en belirgin döngü, n / 2 değerine kadar her adayı dener. n = 10^8 için bu, 5 × 10^7 bölme işlemi demektir. Bölenler çarpımları n olan çiftler hâlinde gelir; bu nedenle yalnızca √n değerine kadar (yaklaşık 10^4 adım) arama yaparken her çiftin iki elemanını da toplayabilirsin.

Her uygun böleni ekle

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

Sezgi

Tanımı izleyin. 1'den başlayarak her d değerini deneyin ve n % d == 0 olduğunda d değerini bir toplamda biriktirin. Sonunda toplamı n ile karşılaştırın. 28 için döngü 1, 2, 4, 7 ve 14 değerlerini toplar ve 1 + 2 + 4 + 7 + 14 = 28 olur.

n / 2 değerinde durabilirsiniz. n'den farklı bir bölenin bölüm sonucu en az 2 olur, dolayısıyla bu bölen n'nin yarısından büyük olamaz. Bu sınır n = 1 durumu için de geçerlidir: döngü sıfır kez çalışır, toplam 0 olarak kalır ve yanıt false olur.

Aralığı yarıya indirmek büyüme oranını değiştirmez. n = 10^8 için döngü yine 5 × 10^7 kez çalışır ve böleni olsun ya da olmasın, bu büyüklükteki her girdi için aynı sayıda çalışır.

Algoritma

total değerini 0 olarak ayarla.
d değerini 1 ile n / 2 arasında döngüye sok.
n % d == 0 ise d değerini total değerine ekle.
total == n olup olmadığını döndür.

def isPerfect(n):
    total = 0
    # No proper divisor of n is larger than n / 2.
    for d in range(1, n // 2 + 1):
        if n % d == 0:
            total += d
    return total == n

Kareköküne kadar bölen çiftlerini topla

Sezgi

d, n'yi bölüyorsa n / d de böler. 28 için çiftler 1 × 28, 2 × 14 ve 4 × 7'dir. Her çiftteki üyelerden biri en fazla √n değerindedir; çünkü √n'den büyük iki sayı çarpıldığında sonuç n'den büyük olur. Bu nedenle √n'ye kadar yapılan bir arama her çifte bir kez ulaşır ve ilerledikçe her iki üyeyi de toplarsın.

İki üyeye dikkat etmek gerekir. 1 × n çifti, kendisi uygun bölen olmayan n'yi de getirir: toplamı 1'den, aramayı ise 2'den başlat. Bu başlangıç n = 1 için yanlıştır; çünkü tek böleni kendisidir. Bu yüzden önce bu değer için false döndür. Ayrıca n bir kare olduğunda kök kendisiyle eşleşir: 36 için 6 × 6, 6'yı iki kez değil bir kez eklemelidir.

Sınırı, tam sayılarla kalacak şekilde d * d ≤ n olarak yaz. n = 10^8 için döngü d = 10^4 değerinde durur; böylece 5 × 10^7 yerine yaklaşık 10^4 kez çalışır.

Algoritma

Eğer n == 1 ise, false döndür.
total değerini 1, d değerini 2 olarak ayarla.
d * d ≤ n olduğu sürece: d, n sayısını bölüyorsa d değerini ekle; n / d değeri d değerinden farklıysa onu da ekle.
Bir sonraki d değerine geç.
total == n olup olmadığını döndür.

def isPerfect(n):
    if n == 1:
        return False
    total = 1  # 1 divides every n > 1; n itself does not count
    d = 2
    while d * d <= n:
        if n % d == 0:
            total += d
            partner = n // d
            if partner != d:  # a square root pairs with itself: add it once
                total += partner
        d += 1
    return total == n

Tuzaklar ve uç durumlar

Eşleşme yöntemi kısadır ve bu yöntemdeki her hata toplamı tam olarak bir bölen kadar değiştirir.

n sayısını da saymak. 1 × n çifti toplamı n kadar artırır ve ardından her sayı, toplamı n'den büyükmüş gibi görünür. Toplamı 1 ile başlatın ve aramaya 2'den başlayın.
1 sayısına mükemmel sayı demek. Toplam 1 ile başlatıldığında, 1 girdisi 1 == 1 karşılaştırmasını yapar. Kendisi hariç bölenlerinin toplamı 0 olduğundan, döngüden önce bu durumu ele alın.
Karekökü iki kez eklemek. 16 sayısının kendisi hariç bölenleri 1, 2, 4 ve 8'dir; bunların toplamı 15 eder. 4'ü iki kez eklemek toplamı 19 yapar.
d * d < n koşulunda durmak. Bu, karekökü tamamen atlar; dolayısıyla 16 içindeki 4 hiçbir zaman sayılmaz.
Sınırı kayan noktalı karekökten almak. Tek duyarlıkta veya çift duyarlıkta 2^53'ün üzerinde, tam kare bir sayının karekökü bir eksik çıkabilir ve bir bölen atlanabilir. d * d ≤ n testi tam sayılarla çalışır ve bu sorunla hiçbir zaman karşılaşmaz.

Sıkça sorulan sorular4

Mükemmel bir sayıyı kontrol etmenin zaman karmaşıklığı nedir?

√n'ye kadar bölen çiftlerini toplamak O(√n) zaman ve O(1) alan alır. n = 10^8 için bu yaklaşık 10^4 adımdır. n / 2'ye kadar her adayı test etmek O(n) zaman alır; aynı girdi için yaklaşık 5 × 10^7 adımdır.

10^8'den küçük kaç mükemmel sayı vardır?

Beş tane: 6, 28, 496, 8128 ve 33550336. Sayıları hızla seyrekleşir. Bir sonraki sayı olan 8589869056, 32 bitlik bir tam sayıya bile sığmaz.

Tek sayılı mükemmel sayılar var mı?

Kimse bilmiyor. Şimdiye kadar bulunan her mükemmel sayı çifttir. Araştırmalar, 10^1500 değerinin altındaki tek mükemmel sayıları elemiştir, ancak bunların var olamayacağını söyleyen bir kanıt yoktur. Fonksiyonunuz, girdinin çift olduğu tahminine değil, tanıma göre çalışmalıdır.

Mükemmel, bol ve eksik sayılar arasındaki fark nedir?

Uygun bölenlerin toplamını sayıyla karşılaştır. Eşitse mükemmeldir; 28 gibi. Daha büyükse bol sayıdır; bölenlerinin toplamı 16 olan 12 gibi. Daha küçükse eksiktir; tek uygun böleni 1 olan her asal sayı gibi.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

n = 28

Beklenen

true