Cari nombor yang tidak boleh dibahagikan dengan mana-mana nombor dalam julat, menggunakan C++

Dalam artikel ini, kita akan membincangkan masalah mencari nombor antara 1 dan n (diberi) yang tidak boleh dibahagikan dengan sebarang nombor antara 2 dan 10. Marilah kita memahami perkara ini dengan beberapa contoh -

Input : num = 14
Output : 3
Explanation: There are three numbers, 1, 11, and 13, which are not divisible.

Input : num = 21
Output : 5
Explanation: There are five numbers 1, 11, 13, 17, and 19, which are not divisible.

Cara untuk menyelesaikan

Kaedah mudah

Jika kita menyemak setiap nombor dari 1 hingga nombor, sama ada ia boleh dibahagi dengan sebarang nombor antara 2 hingga 10. Jika tidak, tambahkan kiraan. Tetapi kaedah ini mengambil terlalu banyak masa, sekali gus meningkatkan kerumitan masa.

Kaedah yang cekap

Cara terbaik yang boleh kita fikirkan ialah mencari nombor dari 1 hingga nombor, yang boleh menjadi sebarang nombor dalam julat [2, 10], dan kemudian tolak kiraan ini daripada nombor.

Jadi pertama, kita perlu mencari semua nombor yang boleh dibahagi dengan 2, 3, 4, 5,10. Tetapi nombor yang boleh dibahagi dengan 4, 6, 8, dan 10 boleh dibahagi dengan 2, dan nombor yang boleh dibahagi dengan 3 boleh dibahagi dengan 6 dan 9.

Kita perlu mencari semua nombor yang boleh dibahagi dengan 2, 3, dan 5. , dan 7. Kita boleh mengiranya berdasarkan prinsip inklusi-pengecualian.

Prinsip Kemasukan-Pengecualian

Ia menyatakan bahawa kita harus memasukkan saiz setiap set individu, anda harus mengeluarkan saiz persimpangan berpasangan, menambah saiz semua persimpangan tiga set, dan sebagainya.

Formula untuk mencari semua nombor ialah,

= NUM – X + Y – Z + A.

di mana,

X = num divisible by 2, 3, 5, 7 ( [num / 2] + [num / 3] + [num / 5] + [num / 7] )

Y = num divisible by (2,3), (2, 5), (2, 7), (3, 5), (3, 5), (3, 7) and (5, 7) = ( [num / (2 * 3)] + [num / (2 * 5)] + [num / (2 * 7)] + [num / (3 * 5)] + num / (3 * 7)] + [num / (5 * 7)] ).

Z = num divisible by (2, 3, 5), (2, 3, 7), (2, 5, 7) and (3, 5, 7) = ( [num / (2 * 3 * 5)] + [num / (2 * 3 * 7)] + [num / (2 * 5 * 7)] + [num / (3 * 5 * 7)] )

A = num divisible by (2, 3, 5, 7) = ( [num / (2 * 3 * 5 * 7)] )

Contoh

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n = 21, result;
   // applying formula from inclusion - exclusion principle
   // to find the count of numbers not divisible by any number from 2 to 10.
   result = n - n / 2 - n / 3 - n / 5 - n / 7
      + n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35
      - n / 30 - n / 42 - n / 70 - n / 105 + n / 210;
   cout << "The count of numbers, not div by [2, 10] is: " << result;

   return 0;
}

Output

The count of numbers, not div by [2, 10] is: 5

Kesimpulan

Dalam artikel ini, kami membincangkan cara mencari nombor yang bukan 2 dan tidak boleh dibahagi. Untuk menyelesaikan masalah ini, kami membincangkan prinsip inklusi-pengecualian. Kami juga membincangkan program C++ untuk menggunakan kaedah ini untuk mendapatkan hasil dalam kerumitan O(1). Anda boleh menulis program ini dalam mana-mana bahasa lain seperti Java, C, Python, dll. Kami berharap artikel ini dapat membantu anda.

Atas ialah kandungan terperinci Cari nombor yang tidak boleh dibahagikan dengan mana-mana nombor dalam julat, menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!