Dalam C++, terjemah yang berikut ke dalam bahasa Cina: Kira bilangan nombor antara L dan R yang secara relatifnya prima kepada P

Dalam dunia pengaturcaraan komputer, mencari bilangan nombor dalam julat tertentu yang bersamaan dengan nombor tertentu boleh menjadi tugas biasa. Nombor perdana relatif, juga dikenali sebagai nombor perdana relatif, ialah nombor yang tidak mempunyai faktor sepunya selain 1. Dalam artikel ini, kita akan meneroka mencari bilangan nombor yang relatif perdana kepada nombor P tertentu antara integer L dan R yang diberikan dengan menggunakan bahasa C++.

Tatabahasa

Kami mula-mula akan menggariskan sintaks kaedah yang akan kami gunakan dalam contoh kod berikut -

int countCoprimes(int L, int R, int P);

Algoritma

Algoritma yang akan kami gunakan untuk mengira bilangan nombor perdana bersama adalah seperti berikut −

• Mulakan kiraan pembolehubah kepada 0, yang digunakan untuk menyimpan kiraan nombor koprima.

• Lelaran setiap nombor nombor bermula dari L hingga R.

• Untuk setiap nombor, semak sama ada ia agak prima dengan P.

• Jika nombor dan P adalah relatif perdana, tambahkan kiraan sebanyak 1.

• Mengembalikan nilai akhir kiraan.

Kaedah 1: Kaedah naif

Kaedah pertama yang akan kita bincangkan ialah kaedah naif. Untuk mengesahkan kesesuaian dengan P menggunakan algoritma Euclidean, kaedah ini memerlukan pemeriksaan berulang setiap nombor dalam julat tertentu.

Contoh

Contoh

#include <iostream>

int countCoprimes(int L, int R, int P) {
   int count = 0;
   for (int num = L; num <= R; num++) {
      int a = num;
      int b = P;
      while (b != 0) {
         int temp = b;
         b = a % b;
         a = temp;
      }
      if (a == 1)
         count++;
   }
   return count;
}

int main() {
   int L = 1; // Set the starting range value
   int R = 100; // Set the ending range value
   int P = 7; // Set the value of P
   
   int result = countCoprimes(L, R, P);
    
   std::cout << "Count of numbers between " << L << " and " << R << " coprime with " << P << ": " << result << std::endl;
   
   return 0;
}

Output

Count of numbers between 1 and 100 coprime with 7: 86

Penjelasan

Penjelasan

Fungsi countCoprimes menerima tiga parameter: L (nilai julat permulaan), R (nilai julat penamat) dan P (nilai P).

Di dalam fungsi countCoprimes, kami memulakan kiraan pembolehubah kepada 0, yang akan menyimpan kiraan coprim.

Gelung for mengulangi setiap nombor nombor dari L ke R.

Dalam gelung, kami memulakan pembolehubah a dan b masing-masing kepada num dan P.

Kami menggunakan algoritma Euclidean dalam gelung sementara untuk mencari pembahagi sepunya terbesar (GCD) a dan b dengan menukar dan melakukan operasi modular berulang kali.

Jika GCD (disimpan dalam a) bersamaan dengan 1, ini bermakna num dan P ialah co-prima. Dalam kes ini, kami menambah pembolehubah kiraan.

Kami memuktamadkan nilai kiraan kami dengan mengulangi semua nombor dengan teliti dan mengembalikannya apabila selesai.

Fungsi utama dengan teliti memberikan nilai yang sesuai kepada pembolehubah L, R dan P.

Kami kemudian memanggil fungsi countCoprimes dengan nilai yang disediakan dan menyimpan hasilnya dalam pembolehubah hasil.

Akhir sekali, kami memaparkan hasilnya, iaitu kiraan nombor antara L dan R yang secara relatifnya prima kepada P.

Kaedah 2: Pemfaktoran Perdana

Strategi ini melibatkan pengeksploitasian pemfaktoran perdana P untuk mengira dengan tepat bilangan integer koprima yang jatuh di antara L dan R.

Contoh

Contoh

#include <iostream>
#include <unordered_set>

int countCoprimes(int L, int R, int P) {
   std::unordered_set<int> factors;
   int tempP = P;

   for (int i = 2; i * i <= tempP; i++) {
      while (tempP % i == 0) {
         factors.insert(i);
         tempP /= i;
      }
   }

   if (tempP > 1)
      factors.insert(tempP);

   int count = 0;
   for (int num = L; num <= R; num++) {
      bool isCoprime = true;
      for (int factor : factors) {
         if (num % factor == 0) {
            isCoprime = false;
            break;
         }
      }
      if (isCoprime)
         count++;
   }

   return count;
}

int main() {
   int L = 1; // Set the starting range value
   int R = 100; // Set the ending range value
   int P = 7; // Set the value of P

   int result = countCoprimes(L, R, P);

   std::cout << "Count of numbers between " << L << " and " << R << " coprime with " << P << ": " << result << std::endl;

   return 0;
}

Output

Count of numbers between 1 and 100 coprime with 7: 86

Penjelasan

Penjelasan

Fungsi countCoprimes menerima tiga parameter: L (nilai julat permulaan), R (nilai julat penamat) dan P (nilai P).

Kami mencipta set faktor tidak tertib untuk menyimpan faktor utama P. Kami memulakan tempP pembolehubah sementara kepada P.

Kami mengulangi daripada 2 kepada punca kuasa dua tempP. Jika tempP boleh dibahagikan dengan i, kami menambah i kepada set faktor dan membahagi tempP dengan i sehingga tempP tidak lagi boleh dibahagikan dengan i.

Jika tempP lebih besar daripada 1 selepas gelung di atas, ini bermakna ia adalah nombor perdana itu sendiri dan harus ditambah kepada faktor.

Kami memulakan kiraan pembolehubah kepada 0, yang akan menyimpan kiraan nombor koprima.

Kami mengulangi setiap nombor nombor dari L ke R dan menyemak sama ada ia boleh dibahagikan dengan mana-mana faktor dalam faktor yang ditetapkan. Jika boleh, kami melabelkannya bukan koprime.

Selepas melengkapkan lelaran semua nombor, kiraan yang terhasil akan dikembalikan sebagai nilai akhir. Bagi fungsi utama, ia memulakan L, R dan P dengan nilai yang ditentukan.

Kami kemudian memanggil fungsi countCoprimes dengan nilai yang disediakan dan menyimpan hasilnya dalam pembolehubah hasil.

Akhir sekali, kami memaparkan hasilnya, iaitu kiraan nombor antara L dan R yang secara relatifnya prima kepada P.

Kesimpulan

Mengira nombor coprime dalam julat L-R yang ditentukan, dan memenuhi nilai P tertentu, adalah cabaran yang baik untuk pengaturcara - tetapi pada tahap kod, apakah pendekatan terbaik? Sebagai sebahagian daripada artikel ini, kami menyelami dua kes penggunaan C++ yang memberikan kecekapan sebenar apabila menyelesaikan masalah seperti ini. Pertama, dengan mengulangi semua nilai dalam selang sasaran dan menggunakan algoritma Euclidean untuk memeriksa sama ada nombor sepadan dengan coprime, selain itu, terdapat juga kaedah fungsi Euler, yang menggunakan strategi pengoptimuman. Tidak kira kaedah yang anda gunakan, sama ada anda boleh memanfaatkannya sepenuhnya bergantung pada faktor kontekstual, seperti nombor yang anda pilih dan selang yang anda tentukan, tetapi memilih dengan bijak antara dua kaedah yang mungkin benar-benar boleh mempercepatkan pelaksanaannya kelajuan program. Bagi pengekod yang ingin menambah kemahiran teknikal kepada kemahiran teknikal dan kebolehan menyelesaikan masalah kreatif mereka, menguasai pengiraan nombor coprime dengan C++ melalui kaedah ini mungkin hanya apa yang mereka perlukan.

Atas ialah kandungan terperinci Dalam C++, terjemah yang berikut ke dalam bahasa Cina: Kira bilangan nombor antara L dan R yang secara relatifnya prima kepada P. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!