Ketahui definisi dahulu
Nombor perdana ialah nombor bulat yang lebih besar daripada 1 dengan tepat dua pembahagi positif: 1 dan nombor itu sendiri. Nombor perdana pertama ialah 2, 3, 5, 7, 11 dan 13. Nombor 1 bukanlah perdana atau komposit, dan 2 ialah satu-satunya perdana genap.
Semak hanya sehingga punca kuasa dua
Untuk menguji integer positif n, anda tidak perlu mencuba setiap nombor di bawah n. Jika n mempunyai faktor yang lebih besar daripada punca kuasa dua, ia juga mesti mempunyai faktor padanan yang lebih kecil daripada punca kuasa dua. Jadi menguji pembahagi yang mungkin sehingga punca kuasa dua sudah memadai.
- Jika nombor itu kurang daripada 2, ia bukan perdana.
- Periksa sama ada ia boleh dibahagikan dengan 2. Jika genap dan lebih besar daripada 2, ia bukan perdana.
- Cuba pembahagi ganjil daripada 3 hingga punca kuasa dua. Jika ada yang membahagi sama rata, bilangannya adalah komposit.
- Jika tiada yang membahagi sama rata, nombor itu adalah perdana.
Contoh: adakah 97 perdana?
Punca kuasa dua bagi 97 adalah kurang sedikit daripada 10. Periksa pembahagi perdana yang mungkin sehingga titik itu: 2, 3, 5 dan 7. Nombor itu tidak boleh dibahagikan dengan mana-mana daripada mereka, jadi 97 ialah perdana.
Untuk 91, cek mendapati 7: 91 ÷ 7 = 13. Itu sudah cukup untuk menunjukkan bahawa 91 adalah komposit; tidak perlu menguji pembahagi yang lebih besar.
Kesilapan biasa
- Memanggil 1 perdana. Sebuah perdana mesti mempunyai dua pembahagi positif, manakala 1 hanya mempunyai satu.
- Dengan mengandaikan setiap nombor ganjil ialah perdana. Komposit ganjil seperti 9, 15, 21 dan 91 mempunyai pembahagi ganjil.
- Menguji hanya beberapa pembahagi kecil untuk nombor yang besar. Semakan mesti meliputi setiap pembahagi yang mungkin sehingga punca kuasa dua, atau menggunakan algoritma primaliti yang disahkan.
UsefulVerse menyemak input nombor bulat praktikal secara setempat dalam penyemak imbas anda. Keputusan utama ialah semakan kebolehbahagi, bukan bukti tentang kunci kriptografi atau pengganti perisian teori nombor khusus.