Nombor berbahaya

Sesuatu nombor dianggap berbahaya jika ia adalah integer positif dan bilangan digit yang ditetapkan dalam pengembangan binarinya adalah perdana. Nombor berbahaya pertama ialah 3 kerana 3 = (11)₂. Dapat dilihat bahawa perwakilan binari 3 mempunyai set bilangan digit 2, iaitu nombor perdana.

10 nombor berbahaya teratas ialah 3, 5, 6, 7, 9, 10, 11, 12, 13, 14. Menariknya, kuasa 2 tidak boleh menjadi nombor yang berbahaya kerana ia sentiasa hanya mempunyai set 1 bit. 1 bukan nombor perdana. Sebaliknya, semua nombor yang boleh dinyatakan sebagai 2ⁿ + 1, di mana n ialah sebarang nombor asli, akan sentiasa menjadi nombor buruk kerana mereka akan mempunyai 2 set bit, dan kita tahu bahawa 2 ialah nombor perdana.

Mengingat sifat nombor berbahaya ini, artikel berikut membincangkan cara untuk menyemak sama ada nombor berbahaya.

Pernyataan Masalah

Soalan ini bertujuan untuk menyemak sama ada nombor n yang diberikan adalah nombor berbahaya, iaitu nombor positif dengan nombor perdana bit set dalam pengembangan binarinya.

Contoh

Input: 37

Output: Pernicious

Terjemahan

Penjelasan

ialah:

Penjelasan

37 = perwakilan binari 100101.

Tetapkan bilangan digit = 3

Memandangkan 3 ialah nombor perdana, 37 ialah nombor buruk.

Input: 22

Output: Pernicious

Terjemahan

Penjelasan

ialah:

Penjelasan

22 = perwakilan binari 10110.

Tetapkan bilangan digit = 3.

Oleh kerana 3 ialah nombor perdana, 22 ialah nombor ganas.

Input: 71

Output: Not Pernicious

Terjemahan

Penjelasan

ialah:

Penjelasan

Perwakilan binari 71 ialah 1000111.

Tetapkan bilangan digit = 4.

Memandangkan 4 bukan nombor perdana, 71 juga bukan nombor buruk.

Input: 64

Output: Not Pernicious

Terjemahan

Penjelasan

ialah:

Penjelasan

Perwakilan binari 64 ialah 1000000.

Tetapkan bilangan digit = 1.

Sejak 64 = 2⁶ iaitu ia adalah kuasa 2, ia mempunyai 1 set bit. Oleh kerana 1 bukan nombor perdana, 64 bukan nombor ganas.

Penyelesaian

Kita mesti tahu sama ada bilangan digit yang ditetapkan ialah nombor perdana untuk menentukan sama ada nombor itu berniat jahat. Tugas utama di tangan adalah untuk mengira bilangan set digit dalam pengembangan binari nombor ini. Kaedah berikut boleh digunakan untuk mengira set nombor digit dan kemudian menentukan sama ada hasilnya ialah nombor perdana.

Kaedahnya merangkumi langkah-langkah berikut -

• Lelaran ke atas semua bit nombor menggunakan operator gelung dan anjakan kanan.

• Jika nilai bit ialah 1, kiraan bit yang ditetapkan dinaikkan sebanyak 1.

• Semak sama ada nilai akhir kiraan ialah nombor perdana.

• Tunjukkan jawapan.

Algoritma

Fungsi is_prime()

• jika (n

kesilapan pemulangan

• untuk (i dari 2 hingga √a)

Jika (a%i==0)

kesilapan pemulangan

• kembali benar

Fungsi count_set_bits()

• Memulakan pembilang = 0

• apabila (n > 0)

• jika ((n & 1) > 0)

• kaunter = kaunter + 1

• n = n >> 1

• Kaunter Pemulangan

Fungsi adalah_pernious()

• Memulakan kaunter

• Pembilang = bilangan_set_bit(n)

• jika (is_prime(counter) == benar)

kembali benar

• Lain-lain

kesilapan pemulangan

Fungsi utama()

• Memulakan n

• jika (is_pernious())

cout

• Lain-lain

cout

• Cetak

Contoh: program C++

Atur cara menggunakan fungsi

is_pernicious()

untuk menentukan sama ada sesuatu nombor itu merosakkan. Ia menganalisis bit paling tidak ketara dalam setiap lelaran gelung dengan mengalihkan nilai ke kanan sebanyak n pada akhir setiap lelaran dalam fungsi

count_set_bits()

. Kemudian, ia memanggil fungsi

is_prime()

untuk mengumpul sama ada bilangan digit yang ditetapkan ialah nombor perdana.

#include <iostream>
using namespace std;
// this function counts the number of set bits by analyzing the rightmost bit using a while loop till n > 0.
// it performs logical & operation between 1 and n to determine if the rightmost bit is set or not.
// if it is set, count is incremented by 1
// right shift the value of n to make the bit left of the rightmost bit, the new rightmost bit.
int count_set_bits(int n){
   int count = 0;
   while (n > 0){
   
      // if the rightmost bit is 1: increment count
      if ((n & 1) > 0){
         count++;
      }
      
      // right shift the value of n to examine the next least significant bit
      n = n >> 1;
   }
   return count;
}

// this function determines if count of set bits in the given number is prime
bool is_prime(int count){
   if (count < 2)
   return false;
   for (int i = 2; i * i < count; i++){
      if (count % i == 0)
      return false;
   }
   return true;
}

// this functions states if count of set bits is prime -> pernicious
bool is_pernicious(int n){
   int count;
   count = count_set_bits(n);
   
   // if count is prime return true
   if (is_prime(count)){
      return true;
   }
   return false;
}

// main function
int main(){
   int n = 11;
   if (is_pernicious(n)){
      cout << n <<" is Pernicious Number";
   }
   else{
      cout << n << " is Non-Pernicious Number";
   }
   return 0;
}

Output

11 is Pernicious Number

Analisis ruang-masa

Kerumitan masa: O(log(n) + sqrt(count)). Dalam fungsi count_set_bits(), gelung melaksanakan log(n) kali semasa kita menganalisis nombor sedikit demi sedikit. Fungsi is_prime() mengambil masa O(sqrt(count)) untuk menyemak sama ada kiraan adalah perdana. Kedua-dua fungsi akan dipanggil sekali semasa pelaksanaan.

Kerumitan ruang: O(1), kerana tiada ruang tambahan digunakan dalam pelaksanaan. Tidak kira saiz nombor input, algoritma sentiasa menggunakan jumlah ruang yang tetap.

Kesimpulan

Nombor buruk ialah konsep matematik yang menarik dan ia boleh dikenal pasti dengan mudah dan berkesan menggunakan kaedah yang dibincangkan di atas. Artikel ini juga menerangkan algoritma yang akan digunakan, penyelesaian program C++ dan analisis kerumitan masa dan ruang.

Atas ialah kandungan terperinci Nombor berbahaya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!