প্রদত্ত কাজটি হল একটি সংখ্যার [1, N] পরিসরে যেখানে N দেওয়া আছে সেখানে সর্বাধিক সংখ্যক অনন্য মৌলিক গুণনীয়ক খুঁজে বের করা।
আসুন এখন বুঝতে পারি একটি উদাহরণ ব্যবহার করে আমাদের কী করতে হবে −
ইনপুট − N=100
আউটপুট৷ − 3
ব্যাখ্যা − চলুন 30 নিই [1, 100]
এর পরিসরে30 =3 * 2 * 5 =অনন্য মৌলিক গুণনীয়ক। অতএব, [1, 100] পরিসরে সর্বাধিক 3টি অনন্য কারণ পাওয়া যেতে পারে।
ইনপুট − N=300
আউটপুট − 4
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
MaxPrime() ফাংশনে আমরা প্রথমে পরীক্ষা করব কিনা (N <2)। যদি তাই হয় তবে কেবল শূন্য দিন, অন্যথায় এগিয়ে যান।
-
তারপর আমরা প্রদত্ত সংখ্যা N এর পূর্বে সমস্ত মৌলিক সংখ্যা বের করতে ইরাটোসথেনিসের চালুনি ব্যবহার করব।
-
পণ্য এবং চূড়ান্ত উত্তর যথাক্রমে সংরক্ষণ করতে দুটি ভেরিয়েবল pro=1 এবং max=0 টাইপ int শুরু করুন।
-
Eratosthenes-এর চালনির ভিতরে আমরা মৌলিক সংখ্যার প্রথম সেটটিকে গুণ করব যতক্ষণ না গুণফল N-এর থেকে ছোট থাকে − pro=*p;
লিখে। -
পরীক্ষা করুন যদি (pro> N)। যদি তাই হয় তাহলে সর্বোচ্চ ফেরত দিন এবং সর্বোচ্চ 1 যোগ করুন।
-
চালনির বাইরে, সর্বাধিক ফেরত দিন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int MaxPrime(int N){
if (N < 2)
return 0;
// Using Sieve of Eratosthenes
bool Arr[N+1];
memset(Arr, true, sizeof(Arr));
int pro = 1, max = 0;
for (int p=2; p*p<=N; p++){
if (Arr[p] == true){
for (int i=p*2; i<=N; i += p)
Arr[i] = false;
/*Multiply first set of prime numbers while product remains smaller than N*/
pro *= p;
if (pro > N)
return max;
max++;
}
}
return max;
}
//Main function
int main(){
int N = 300;
cout << MaxPrime(N);
return 0;
} আউটপুট
আমরা উপরের কোডটি চালালে আমরা নিম্নলিখিত আউটপুট পাব −
4
