এই প্রবন্ধে, আমরা 1 থেকে n (প্রদত্ত) সংখ্যাগুলি খুঁজে বের করার সমস্যা নিয়ে আলোচনা করব যেগুলিকে 2 থেকে 10 পর্যন্ত কোনও সংখ্যা দিয়ে ভাগ করা যায় না৷ আসুন কিছু উদাহরণ দিয়ে এটি বোঝা যাক −
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.
সমাধান খোঁজার পদ্ধতি
সরল পদ্ধতি
যদি আমরা 1 থেকে সংখ্যা পর্যন্ত প্রতিটি সংখ্যা পরীক্ষা করি, এটি 2 থেকে 10 পর্যন্ত যেকোনো সংখ্যা দ্বারা ভাগ করা যায় কিনা। যদি না হয়, তাহলে গণনা বৃদ্ধি করুন। কিন্তু এই পদ্ধতিতে অনেক বেশি সময় লাগবে তাই সময়ের জটিলতা বাড়বে।
দক্ষ পদ্ধতি
আমরা যে সর্বোত্তম পদ্ধতির কথা ভাবতে পারি তা হল প্রথমে 1 থেকে num পর্যন্ত সংখ্যাগুলি খুঁজে বের করা, পরিসরের যেকোন সংখ্যা দ্বারা বিভাজ্য [ 2, 10 ], তারপর এই গণনাটি সংখ্যা দিয়ে বিয়োগ করুন৷
তাই প্রথমে, আমাদের 2, 3, 4, 5,10 দ্বারা বিভাজ্য সমস্ত সংখ্যা খুঁজে বের করতে হবে। কিন্তু 4, 6, 8, এবং 10 দ্বারা বিভাজ্য সংখ্যাগুলি 2 দ্বারা বিভাজ্য এবং তিনটি দ্বারা বিভাজ্য সংখ্যাগুলি 6 এবং 9 দ্বারা বিভাজ্য৷
আমাদের 2, 3, 5, এবং 7 দ্বারা বিভাজ্য সমস্ত সংখ্যা খুঁজে বের করতে হবে। এবং এটি আমরা অন্তর্ভুক্তি-বর্জন নীতি থেকে গণনা করতে পারি।
অন্তর্ভুক্তি-বর্জনের নীতি
এটি বলে যে আমাদের প্রতিটি একক সেটের আকার অন্তর্ভুক্ত করা উচিত, আপনার জোড়াযুক্ত ছেদটির আকার সরানো উচিত, তিনটি সেটের সমস্ত ছেদগুলির আকার যোগ করা উচিত, ইত্যাদি৷
সমস্ত সংখ্যা খুঁজে বের করার সূত্র হল,
= NUM – X + Y – Z + A.
কোথায়,
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)] )
উদাহরণ
#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;
} আউটপুট
The count of numbers, not div by [2, 10] is: 5
উপসংহার
এই নিবন্ধে, আমরা 2 থেকে n পর্যন্ত অ-বিভাজ্য সংখ্যা খুঁজে বের করার উপায় নিয়ে আলোচনা করেছি। এই সমস্যা সমাধানের জন্য, আমরা অন্তর্ভুক্তি-বর্জন নীতি নিয়ে আলোচনা করেছি। O(1) জটিলতার সাথে ফলাফল পেতে পদ্ধতি প্রয়োগ করার জন্য আমরা C++ প্রোগ্রাম নিয়েও আলোচনা করেছি। আপনি এই প্রোগ্রামটি জাভা, সি, পাইথন, ইত্যাদির মতো অন্য যেকোনো ভাষায় লিখতে পারেন। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে।
