Perfect Number

Q: Apa kompleksitas waktu untuk memeriksa bilangan sempurna?

Mengumpulkan pasangan pembagi hingga √n membutuhkan waktu O(√n) dan ruang O(1) , sekitar 10^4 langkah untuk n = 10^8 . Menguji setiap kandidat hingga n / 2 membutuhkan waktu O(n) , sekitar 5 × 10^7 langkah untuk input yang sama.

Q: Apakah ada bilangan sempurna ganjil?

Tidak ada yang tahu. Setiap bilangan sempurna yang ditemukan sejauh ini adalah genap, dan pencarian telah menyingkirkan bilangan ganjil di bawah 10^1500 , tetapi belum ada bukti yang menyatakan bahwa bilangan ganjil tidak mungkin ada. Fungsimu harus bekerja berdasarkan definisinya, bukan berdasarkan dugaan bahwa inputnya genap.

Q: Apa perbedaan antara bilangan sempurna, berlimpah, dan kurang?

Bandingkan jumlah pembagi sejati dengan bilangannya. Jika sama, bilangan itu sempurna, seperti 28 . Jika lebih besar, bilangan itu berlimpah, seperti 12 , yang jumlah pembaginya adalah 16 . Jika lebih kecil, bilangan itu kurang, seperti setiap bilangan prima, yang hanya memiliki 1 sebagai pembagi sejatinya.

PemulaMatematika dan simulasi

+10

Faktor sejati dari n adalah faktor positif yang lebih kecil daripada n itu sendiri. Bilangan sempurna sama dengan jumlah faktor sejatinya: 6 = 1 + 2 + 3. Kamu mendapatkan bilangan bulat positif n. Kembalikan true jika n sempurna dan false jika tidak.

Fungsi

isPerfect(n: integer) → boolean

ninteger: bilangan bulat positif yang akan diuji
Mengembalikanboolean: benar jika n sama dengan jumlah pembagi sejatinya, salah jika tidak

Batasan

1 ≤ n ≤ 10⁸

Contoh

Input: n = 28
Output: true
Penjelasan: Pembagi sejati dari 28 adalah 1, 2, 4, 7, dan 14. Jumlah semuanya adalah 28, jadi 28 adalah bilangan sempurna.

Input: n = 12
Output: false
Penjelasan: Faktor sejati dari 12 adalah 1, 2, 3, 4, dan 6. Jumlahnya adalah 16, yang melebihi 12.

Input: n = 1
Output: false
Penjelasan: 1 sama sekali tidak memiliki pembagi sejati, jadi jumlahnya adalah 0, bukan 1.

Pertanyaan lanjutan

Setiap bilangan sempurna genap berbentuk 2^(p-1) × (2^p-1), dengan 2^p-1 adalah bilangan prima. Bisakah kamu mencantumkan semua bilangan sempurna di bawah 10^8 dengan rumus itu, tanpa menguji setiap bilangan?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Mencoba setiap kandidat pembagi hingga n / 2 membutuhkan 5 × 10^7 operasi pembagian saat n = 10^8. Pembagi muncul berpasangan dan hasil kali setiap pasangan adalah n, jadi cari hanya hingga √n, sekitar 10^4 langkah, lalu tambahkan kedua anggota setiap pasangan.

Tambahkan semua pembagi sejati

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Ikuti definisinya: coba setiap d dari 1 hingga n / 2, lalu tambahkan nilai yang membagi n. Untuk 28, cara ini menemukan 1, 2, 4, 7, dan 14. Tidak ada pembagi sejati yang lebih besar dari n / 2, karena hasil baginya setidaknya 2. Batas ini juga menangani n = 1: perulangan berjalan nol kali dan totalnya tetap 0.

Membagi dua rentang tidak mengubah pertumbuhannya. Perulangan berjalan n / 2 kali pada setiap input, baik pembagi maupun bukan.

Algoritma

Atur total menjadi 0.
Ulangi d dari 1 hingga n / 2.
Jika n % d == 0, tambahkan d ke total.
Kembalikan apakah total == n.

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

Kumpulkan pasangan pembagi hingga akar kuadrat

Intuisi

Jika d membagi n, maka n / d juga membagi n: untuk 28, pasangan pembaginya adalah 1 × 28, 2 × 14, dan 4 × 7. Salah satu anggota setiap pasangan bernilai paling besar √n, karena hasil kali dua bilangan yang lebih besar dari √n melebihi n. Jadi, pencarian hingga √n menemukan setiap pasangan tepat satu kali, lalu kamu menjumlahkan kedua anggotanya.

Pasangan 1 × n menyertakan n itu sendiri, yang bukan pembagi sejati, jadi mulai total dari 1 dan pencarian dari 2. Akar kuadrat berpasangan dengan dirinya sendiri dan dihitung satu kali. Tuliskan batasnya sebagai d * d ≤ n agar tetap menggunakan bilangan bulat; untuk n = 10^8, perulangan berhenti pada d = 10^4.

Algoritma

Jika n == 1, kembalikan false.
Atur total ke 1 dan d ke 2.
Selama d * d ≤ n: jika d membagi n, tambahkan d, dan tambahkan juga n / d jika nilainya berbeda dari d.
Lanjutkan ke d berikutnya.
Kembalikan apakah total == n.

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

Jebakan dan kasus tepi

Menghitung n itu sendiri melalui pasangan 1 × n. Setiap jumlah kemudian melebihi n: 28 berjumlah 56.
Menganggap 1 sebagai bilangan sempurna. Jika total dimulai dari 1, input 1 dibandingkan dengan 1 == 1, tetapi jumlah pembagi sejatinya adalah 0.
Menambahkan akar kuadrat dua kali. Jumlah pembagi sejati dari 16 adalah 15; menambahkan 4 dua kali menghasilkan 19.
Melakukan perulangan selama d * d < n. Ini melewatkan akar, sehingga 4 dari 16 tidak pernah dihitung.
Mengambil batas dari akar kuadrat floating point. Dalam presisi tunggal, akar dari kuadrat sempurna bisa kurang satu sehingga sebuah pembagi terlewat.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu untuk memeriksa bilangan sempurna?

Mengumpulkan pasangan pembagi hingga √n membutuhkan waktu O(√n) dan ruang O(1), sekitar 10^4 langkah untuk n = 10^8. Menguji setiap kandidat hingga n / 2 membutuhkan waktu O(n), sekitar 5 × 10^7 langkah untuk input yang sama.

Apakah ada bilangan sempurna ganjil?

Tidak ada yang tahu. Setiap bilangan sempurna yang ditemukan sejauh ini adalah genap, dan pencarian telah menyingkirkan bilangan ganjil di bawah 10^1500, tetapi belum ada bukti yang menyatakan bahwa bilangan ganjil tidak mungkin ada. Fungsimu harus bekerja berdasarkan definisinya, bukan berdasarkan dugaan bahwa inputnya genap.

Apa perbedaan antara bilangan sempurna, berlimpah, dan kurang?

Bandingkan jumlah pembagi sejati dengan bilangannya. Jika sama, bilangan itu sempurna, seperti 28. Jika lebih besar, bilangan itu berlimpah, seperti 12, yang jumlah pembaginya adalah 16. Jika lebih kecil, bilangan itu kurang, seperti setiap bilangan prima, yang hanya memiliki 1 sebagai pembagi sejatinya.

def isPerfect(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

n = 28

Output yang diharapkan

true