ধারণা
প্রদত্ত দুটি সংখ্যা P এবং Q ( P এবং Q 10^6 পর্যন্ত হতে পারে) যা একটি সংখ্যাN =(P!/Q!) গঠন করে। আমাদের কাজ হল সম্ভাব্য সর্বাধিক সংখ্যক অপারেশন সম্পাদন করে N 1 থেকে কমানো। মনে রাখবেন, প্রতিটি অপারেশনে, একজন N কে N/X দিয়ে প্রতিস্থাপন করতে পারে যদি N X দ্বারা বিভাজ্য হয়। সম্ভব হতে পারে এমন সর্বাধিক সংখ্যক অপারেশন নির্ধারণ করুন।
ইনপুট
A = 7, B = 4
আউটপুট
4
ব্যাখ্যা
N হল 210 এবং ভাজক হল 2, 3, 5, 7
ইনপুট
A = 3, B = 1
আউটপুট
2
ব্যাখ্যা
N হল 6 এবং ভাজক হল 2,3৷
পদ্ধতি
এটা লক্ষ্য করা গেছে যে P!/Q সংখ্যার ফ্যাক্টরাইজেশন! এটা কি সংখ্যার ফ্যাক্টরাইজেশন (Q + 1)*(Q + 2)*…*(P – 1)*P।
এটাও লক্ষ করা উচিত, যদি আমরা শুধুমাত্র এর মৌলিক গুণনীয়কগুলির সাথে N দিয়ে ভাগ করি তাহলে ক্রিয়াকলাপের সংখ্যা সর্বাধিক হবে। এর ফলস্বরূপ, অন্য কথায় আমাদের N এর মৌলিক গুণনীয়কগুলির গণনা নির্ধারণ করতে হবে যার মধ্যে ডুপ্লিকেটগুলিও রয়েছে৷
2 থেকে 1000000 পর্যন্ত প্রতিটি সংখ্যার গুণিতককরণে মৌলিক গুণনীয়কের সংখ্যা গণনা করুন।
প্রথমে, Sieve of Eratosthenes প্রয়োগ করুন এই সংখ্যাগুলির প্রতিটির একটি মৌলিক ভাজক নির্ধারণ করার জন্য। এটি নিম্নরূপ ব্যাখ্যা করা হয়েছে −
-
2 থেকে N পর্যন্ত ধারাবাহিক পূর্ণসংখ্যার একটি তালিকা তৈরি করুন:(2, 3, 4, …, N)।
-
প্রথমে, অনুমান করুন p সমান 2, প্রথম মৌলিক সংখ্যা।
-
p^2 থেকে শুরু করে, p এর বৃদ্ধিতে গণনা করুন এবং তালিকায় p^2 এর থেকে বড় বা সমান এই সংখ্যাগুলির প্রতিটি নির্দেশ করুন। সুতরাং, এই সংখ্যাগুলি p(p+1), p(p+2), p(p+3), ইত্যাদি হতে পারে।
-
তালিকায় p এর চেয়ে বড় প্রথম সংখ্যাটি নির্ধারণ করুন যা নির্দেশিত নয়। এটা দেখা গেছে যে এই ধরনের কোন সংখ্যা না থাকলে, বন্ধ করুন। অন্যথায়, অনুমান করুন p এখন এই সংখ্যার সমান (যা পরবর্তী প্রাইম নির্দেশ করে), এবং আবার ধাপ 3 থেকে পুনরাবৃত্তি করুন।
Eratosthenes পদ্ধতির চালনি প্রয়োগ করার পর আমরা নিম্নলিখিত সূত্রটি বাস্তবায়নকারী একটি ফ্যাক্টরাইজেশনের মূল ফ্যাক্টরগুলির সংখ্যা গণনা করতে পারি -
primefactors[num] =primefactors[num / primedivisor[num]] + 1বর্তমানে, কেউ প্রাইম ফ্যাক্টরের জন্য উপসর্গ যোগ অ্যারে প্রয়োগ করতে পারে এবং তারপর ওনান ব্যবধান [P, Q] যোগফলের জন্য উত্তর দিতে পারে।
উদাহরণ
// CPP program to find maximum
// number moves possible
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
// Used to store number of prime
// factors of each number
int primeFactors1[N];
// Shows Function to find number of prime
// factors of each number
void findPrimeFactors(){
for (int a = 2; a < N; a++)
// Now if a is a prime number
if (primeFactors1[a] == 0)
for (int b = a; b < N; b += a)
// Now increase value by one from
// it's preveious multiple
primeFactors1[b] = primeFactors1[b / a] + 1;
// Build prefix sum
// this will be helpful for
// multiple test cases
for (int a = 1; a < N; a++)
primeFactors1[a] += primeFactors1[a - 1];
}
// Driver Code
int main(){
// Create primeFactors1 array
findPrimeFactors();
int P = 7, Q = 4;
// required answer
cout << primeFactors1[P] - primeFactors1[Q];
return 0;
} আউটপুট
4
