Selepas menukar nombor perduaan yang diberi kepada asas antara L dan R, hitung bilangan nombor perdana

Tajuk "Pengiraan nombor perdana selepas menukar nombor binari yang diberikan antara L dan R" merujuk kepada masalah matematik yang melibatkan penukaran nombor binari kepada asas antara L dan R dan kemudian mengira nombor dari antara L dan R Bilangan nombor perdana. Tukar. Dalam matematik, nombor perdana ialah integer yang lebih besar daripada 1 yang hanya boleh dibahagi dengan 1 dan dirinya sendiri.

Untuk menukar nombor binari kepada nombor dalam asas yang berbeza, anda perlu menulis nombor dalam sistem nombor yang berbeza. Asas sistem nombor ialah bilangan nombor unik, dan penukaran dicapai dengan mencari perwakilan setara nombor itu dalam pangkalan baharu. Pengiraan nombor perdana selepas transformasi ialah masalah teori nombor yang sukar yang mempunyai kegunaan dalam kriptografi, sains komputer dan bidang lain. Untuk menyelesaikan masalah ini anda perlu tahu banyak tentang teori nombor, nombor perdana dan sistem nombor.

Apakah nombor perdana?

Sesuatu nombor dipanggil perdana hanya jika ia boleh dibahagi dengan 1 dan nombor itu sendiri. Sebagai contoh, nombor 5 adalah perdana kerana ia hanya boleh dibahagi dengan nombor 1 dan 5, tetapi 6 bukan perdana kerana ia juga boleh dibahagikan dengan 2 dan 3.

Nombor prima hanyalah bertanya berapa bilangan prima yang terdapat dalam set nombor tertentu. Sebagai contoh, ambil satu set nombor {1,2,3,4,5,6,7,8,9}. Dalam set nombor ini, bilangan nombor perdana ialah 4, dan ia adalah 2, 3, 5 , dan 7. Tambahan pula, 1 bukanlah nombor perdana kerana satu-satunya faktor positifnya ialah 1 itu sendiri.

Kaedah

Terdapat dua cara utama untuk mengira masalah nombor perdana seperti yang ditunjukkan di bawah −

• Kaedah ganas

• Pemfaktoran Perdana

Algoritma

Langkah 1 - Masukkan nombor binari dan julat untuk asas L dan R.

Langkah 2 - Ulangi setiap tapak antara L dan R (termasuk).

Langkah 3 - Tukar nombor binari kepada asas semasa.

Langkah 4 − Semak sama ada nombor yang ditukar ialah nombor perdana.

Langkah 5 - Jika nombor yang ditukar ialah nombor perdana, tambahkan kiraan nombor perdana sebanyak 1.

Langkah 6 - Ulang langkah 3-5 untuk semua tapak dalam julat L hingga R.

Langkah 7 − Kembalikan jumlah bilangan nombor perdana yang diperolehi.

Diberikan di bawah ialah pseudokod algoritma -

input: binary number b, range of bases L and R
output: count of prime numbers in the given range

Number_of_prime = 0
for base = L to R
convert b to base
if number_is_prime(converted_number)
   Number_of_prime ++
return Number_of_prime

number_is_prime() ialah kaedah yang menerima nombor sebagai input dan mengembalikan nilai boolean yang menunjukkan sama ada nombor itu adalah perdana.

Kaedah 1: Penyelesaian ganas

Pendekatan Brute Force melibatkan penukaran nombor binari ke dalam setiap asas dari L ke R dan mengira bilangan nombor perdana dalam setiap penukaran. Untuk nombor yang lebih besar, semua kemungkinan variasi perlu disemak, yang boleh memakan masa.

Kod di bawah mengandungi tiga fungsi. Fungsi pertama ialah "isPrime" yang mengembalikan 1 jika nombor input adalah perdana dan 0 sebaliknya. Fungsi kedua "binaryToDecimal" menukar nombor binari kepada nombor perpuluhan. Fungsi ketiga "countPrimes" mengira bilangan nombor perdana yang diperoleh dengan menukar nombor binari antara julat input kepada nombor perpuluhan. Akhir sekali, fungsi utama mengambil nombor binari dan julat nombor, memanggil fungsi "countPrimes" dan mencetak kiraan nombor perdana.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Kod ini menyediakan nilai yang dipratentukan untuk nombor binari dan julat L dan R. Dalam contoh ini saya menggunakan nombor binari 1010 dan julat 5 hingga 20. Anda boleh menukar nilai ini dalam fungsi utama mengikut keperluan.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// Function to check if a number is prime or not
int isPrime(int n) {
   int i;
   for(i = 2; i <= sqrt(n); i++) {
      if(n%i == 0) {
         return 0;
      }
   }
   return 1;
}

// Function to convert binary to decimal
int binaryToDecimal(int n) {
   int decimal = 0, i = 0, remainder;
   while(n != 0) {
      remainder = n % 10;
      n /= 10;
      decimal += remainder * pow(2, i);
      ++i;
   }
   return decimal;
}

// Function to count primes in a given range
int countPrimes(int L, int R) {
   int count = 0, i;
   for(i = L; i <= R; i++) {
      int decimal = binaryToDecimal(i);
      if(isPrime(decimal)) {
         count++;
      }
   }
   return count;
}

// Main function
int main() {
   int binary = 1010; // Example binary number
   int L = 5;         // Example range lower limit
   int R = 20;        // Example range upper limit

   // Count primes and print result
   int count = countPrimes(L, R);
   printf("Number of primes after converting %d to base between %d and %d is: %d\n", binary, L, R, count);

   return 0;
}

Output

Number of primes after converting 1010 to base between 5 and 20 is: 7

Kaedah 2: Pemfaktoran Perdana

Pemfaktoran perdana melibatkan mencari faktor perdana bagi nombor yang diubah dan menyemak sama ada ia berada dalam julat perdana. Ia boleh menjadi kaedah yang cekap untuk nombor yang lebih kecil, tetapi boleh menjadi mahal dari segi pengiraan untuk nombor yang lebih besar.

Kod di bawah mentakrifkan dua fungsi, isPrime() dan countPrimes(), yang menyemak sama ada nombor yang diberikan ialah nombor perdana atau mengira bilangan prima sebelum nombor tertentu. Fungsi utama menerima nombor perduaan dan had radix yang dimasukkan oleh pengguna, menukar nombor perduaan kepada perpuluhan, dan kemudian menukarnya kepada radix berbeza dalam had yang diberikan. Untuk setiap penukaran, program mencari faktor utama dan, jika ia berada dalam had asas semasa, menambah pembilang. Akhirnya, program mencetak bilangan prima yang ditemui. Kod ini mengimport input/output standard dan perpustakaan boolean.

Terjemahan bahasa Cina bagi

Code

ialah:

code

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(int n) {
   if (n <= 1) {
      return false;
   }
   int i;
   for (i = 2; i <= sqrt(n); i++) {
      if (n % i == 0) {
         return false;
      }
   }
   return true;
}

int main() {
   int binaryNum = 110101; // Predefined binary number input
   int L = 3; // Predefined lower limit of base
   int R = 6; // Predefined upper limit of base

   int decimalNum = 0, base = 1;
   while (binaryNum > 0) {
      int digit = binaryNum % 10;
      decimalNum += digit * base;
      base *= 2;
      binaryNum <span>/</span>= 10;
   }

   int transformedNum, factor;
   int primeCount = 0;
   for (int baseNum = L; baseNum <= R; baseNum++) {
      transformedNum = decimalNum;
      while (transformedNum > 1) {
         for (int i = 2; i <= transformedNum; i++) {
            if (transformedNum % i == 0) {
               factor = i;
               break;
            }
         }
         transformedNum <span>/</span>= factor;
         if (isPrime(factor) && factor >= baseNum) {
            primeCount++;
         }
      }
   }
   printf("Count of primes after converting the given binary number in base between L to R is: %d", primeCount);
   return 0;
}

Output

Count of primes after converting the given binary number in base between L to R is: 4

Kesimpulan

Untuk meringkaskan, kita boleh menentukan bilangan nombor perdana dengan terlebih dahulu menukar nombor perduaan yang diberikan kepada asas antara L dan R, dan kemudian mengira bilangan nombor perdana dalam julat itu.

Atas ialah kandungan terperinci Selepas menukar nombor perduaan yang diberi kepada asas antara L dan R, hitung bilangan nombor perdana. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!