Check Prime Number

Q: Apa kompleksitas waktu untuk memeriksa apakah suatu bilangan adalah bilangan prima?

Pembagian percobaan hingga √n membutuhkan waktu O(√n) dan ruang O(1) . Untuk n hingga 2^31-1 , jumlahnya paling banyak sekitar 46,000 pembagian, atau 23,000 jika kamu melewati pembagi genap.

Q: Apakah 1 adalah bilangan prima?

Tidak. Bilangan prima memiliki tepat dua pembagi yang berbeda, yaitu 1 dan dirinya sendiri, sedangkan 1 hanya memiliki satu pembagi. Dengan tidak menyertakan 1 , faktorisasi setiap bilangan bulat menjadi bilangan prima tetap unik.

Q: Apakah ada cara yang lebih cepat untuk menguji apakah bilangan yang sangat besar adalah bilangan prima?

Untuk satu angka 32-bit, pembagian percobaan hingga √n cukup cepat. Untuk angka dengan puluhan digit, program menggunakan tes Miller-Rabin, yang memeriksa beberapa pangkat modular alih-alih mencoba pembagi. Untuk membuat daftar semua bilangan prima hingga batas tertentu, Saringan Eratosthenes lebih unggul daripada menguji setiap angka satu per satu.

PemulaMatematika dan simulasi

+10

Bilangan prima adalah bilangan bulat yang lebih besar dari 1 dan hanya memiliki pembagi 1 serta dirinya sendiri. Kamu mendapatkan bilangan bulat positif n. Kembalikan true jika n adalah bilangan prima dan false jika tidak. Bilangan 1 bukan bilangan prima.

Fungsi

isPrime(n: integer) → boolean

ninteger: bilangan bulat positif yang akan diuji
Mengembalikanboolean: true jika n adalah bilangan prima, false jika tidak

Batasan

1 ≤ n ≤ 2³¹ - 1

Contoh

Input: n = 29
Output: true
Penjelasan: Tidak ada 2, 3, 4, atau 5 yang membagi 29, dan 6 × 6 = 36 sudah lebih besar dari 29, jadi tidak ada pembagi lagi yang perlu ditemukan. 29 adalah bilangan prima.

Input: n = 1
Output: false
Penjelasan: Bilangan prima memiliki tepat dua pembagi, yaitu 1 dan dirinya sendiri. 1 hanya memiliki satu pembagi, jadi jawabannya adalah false.

Input: n = 91
Output: false
Penjelasan: 91 tampak prima, tetapi 7 × 13 = 91. Pembagi 7 ditemukan sebelum pencarian melewati √91 ≈ 9.5.

Pertanyaan lanjutan

Setiap bilangan prima yang lebih besar dari 3 berbentuk 6k-1 atau 6k+1. Bisakah kamu memanfaatkan hal itu untuk menguji hanya sepertiga dari kandidat pembagi?

Petunjuk

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

0 dari 3 dibuka

Solusi

Menguji setiap pembagi dari 2 hingga n-1 membutuhkan lebih dari dua miliar pembagian untuk input bilangan prima terbesar. Pembagi datang berpasangan dan hasil kali setiap pasangan sama dengan n, dan bilangan yang lebih kecil dari setiap pasangan paling besar √n. Jadi, kamu hanya perlu mencari hingga √n: paling banyak sekitar 23,000 bilangan ganjil yang menjadi kandidat.

Coba setiap pembagi

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Uji setiap kandidat d dari 2 hingga n-1 dengan n % d == 0 dan kembalikan false saat pertama kali ditemukan pembagi. Inilah definisi bilangan prima, jadi cara ini benar setelah kamu mengembalikan false untuk n < 2.

Bilangan prima lolos dari setiap pengujian, jadi perulangan berjalan hingga selesai. Untuk n = 2147483647, yang merupakan bilangan prima, jumlahnya sekitar 2.1 × 10^9 pembagian.

Algoritma

Jika n < 2, kembalikan false.
Ulangi d dari 2 hingga n-1.
Jika n % d == 0, kembalikan false.
Setelah perulangan, kembalikan true.

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

Pembagian percobaan hingga akar kuadrat

Intuisi

Jika d membagi n, maka n / d juga membagi n. Keduanya tidak mungkin lebih besar dari √n, karena hasil kalinya akan lebih besar dari n. Jadi, bilangan komposit n selalu memiliki pembagi yang paling besar √n: untuk 91, pasangannya adalah 7 dan 13, dan 7 ≤ 9.5. Jika tidak ada bilangan hingga √n yang membagi n, maka n adalah bilangan prima.

Tuliskan batasnya sebagai d * d ≤ n, yang tetap menggunakan bilangan bulat tanpa pembulatan. Tangani 2 secara terpisah, karena bilangan genap n hanya prima jika nilainya 2. Bilangan ganjil n hanya memiliki pembagi ganjil, jadi mulai dari 3 dan naik dengan langkah 2. Untuk n = 2147483647, perulangan berjalan sekitar 23,000 kali.

Algoritma

Jika n < 2, kembalikan false.
Jika n genap, kembalikan apakah n == 2.
Mulai d dari 3 dan lakukan perulangan selama d * d ≤ n, gunakan tipe 64-bit untuk d.
Jika n % d == 0, kembalikan false. Jika tidak, tambahkan 2 ke d.
Setelah perulangan, kembalikan true.

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

Jebakan dan kasus tepi

Mengembalikan true untuk 1. Angka ini hanya memiliki satu pembagi, bukan dua, jadi bukan bilangan prima.
Menolak 2 karena genap. Periksa n == 2 sebelum kamu menyingkirkan bilangan genap.
Melakukan perulangan saat d * d < n, bukan ≤. Akibatnya, kuadrat bilangan prima seperti 9 dan 49 dianggap sebagai bilangan prima.
Overflow pada d * d. Dalam int 32-bit, 46341 × 46341 meluap menjadi angka negatif, sehingga perulangan berjalan jauh melewati √n. Gunakan tipe 64-bit untuk d, atau bandingkan d ≤ n / d.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu untuk memeriksa apakah suatu bilangan adalah bilangan prima?

Pembagian percobaan hingga √n membutuhkan waktu O(√n) dan ruang O(1). Untuk n hingga 2^31-1, jumlahnya paling banyak sekitar 46,000 pembagian, atau 23,000 jika kamu melewati pembagi genap.

Apakah 1 adalah bilangan prima?

Tidak. Bilangan prima memiliki tepat dua pembagi yang berbeda, yaitu 1 dan dirinya sendiri, sedangkan 1 hanya memiliki satu pembagi. Dengan tidak menyertakan 1, faktorisasi setiap bilangan bulat menjadi bilangan prima tetap unik.

Apakah ada cara yang lebih cepat untuk menguji apakah bilangan yang sangat besar adalah bilangan prima?

Untuk satu angka 32-bit, pembagian percobaan hingga √n cukup cepat. Untuk angka dengan puluhan digit, program menggunakan tes Miller-Rabin, yang memeriksa beberapa pangkat modular alih-alih mencoba pembagi. Untuk membuat daftar semua bilangan prima hingga batas tertentu, Saringan Eratosthenes lebih unggul daripada menguji setiap angka satu per satu.

def isPrime(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

n = 29

Output yang diharapkan

true