একটি সংখ্যার ফ্যাক্টোরিয়ালের মোট ডিভিজর(NOD of Factorial of N)

একটি সংখ্যার ফ্যাক্টোরিয়ালের মোট ডিভিজর বের করতে হয় কীভাবে, এই পর্বে সেটি শিখব আজকে। এটি আমরা ব্রুট ফোরস উপায়ে করতে পারি। প্রথমে সংখ্যাটির ফ্যাক্টোরিয়াল বের করে তারপর এর ডিভিজর গুলো বের করতে পারি। কিন্তু সমস্যা হচ্ছে, সংখ্যাটি যদি 20 এর থেকে বড় হয় তাহলেই long long ডাটা টাইপেও আটবে না। যদি সংখ্যাটি 100 হয় তাহলে এর ফ্যাক্টোরিয়াল হবে 158 ডিজিটের একটি সংখ্যা!!! 

একটি সংখ্যার ফ্যাক্টোরিয়াল হচ্ছে 1 থেকে সেই সংখ্যা পর্যন্ত সবগুলো সংখ্যার গুণফল। তাহলে এখন একটি প্রশ্ন, সংখ্যাটির ফ্যাক্টোরিয়ালের কোন একটি প্রাইম ডিভিজর ও  কি সেই সংখ্যাটির থেকে বর হবে?  উত্তর হচ্ছে, হবে না। সংখ্যাটির ফ্যাক্টোরিয়াল নিজেও কখনো প্রাইম হবে না। কারণ, ফ্যাক্টোরিয়াল টি ত আসলে 1 থেকে n পর্যন্ত সংখ্যা গুলোর গুণফল। একই ভাবে n এর থেকে বড় অন্য কোন ডিভিজর ও 1 থেকে n পর্যন্ত কোন না কোন সংখ্যার গুণফল হবেই। তাহলে এখন আমরা নিশ্চিত হলাম প্রাইম ডিভিজর গুলো 1 থেকে n এর ভিতরেই আছে, মানে আমরা প্রাইম ফ্যাক্টর গুলো পেয়ে গেলাম।

এখন তাহলে আমরা প্রাইম ফ্যাক্টরাইজ করে সহজেই মোট ডিভিজর বের করে ফেলতে পারব। তবে সামনে যাওয়ার আগে নিচের বিষয় গুলো অবশ্যই জানা থাকতে হবে। 

প্রাইম নাম্বার বের করার জন্য সিভ অ্যালগরিদম, 
প্রাইম ফ্যাক্টরাইজেশন, ***
log(n) সময়ে একটি সংখ্যার মোট ডিভিজর বের করা, ***
এবং মডুউলো নিয়ে বেসিক জ্ঞান। 

এখন প্রশ্ন হচ্ছে, শুধু প্রাইম ডিভিজর গুলো গুণ করলে ত আর ফ্যাক্টোরিয়াল পাওয়া যাবে না। একটি প্রাইম কতবার এসেছে মানে, প্রাইম গুলোর পাওয়ার কত সেটি বের করব কীভাবে? এখানেই আসলে মূল পার্থক্য সাধারণ NOD() ফাংশনের সাথে। তাহলে, একটি প্রাইম কতবার এসেছে সেটি বের করতে পারি আমরা Legendre's Formula ব্যবহার করে। এই ফর্মুলাতে বলা হয়েছে একটি প্রাইমের সবথেকে বড় পাওয়ার যেটি n এর ফ্যাক্টোরিয়াল কে ভাগ করতে পারে তা বের করতে হলে ঐ প্রাইমের পাওয়ার গুলো দিয়ে ততক্ষণ ভাগ করতে হবে যতক্ষষণ ভাগফল শূন্য হয় এবং ভাগফল গুলোর যোগফল ই হচ্ছে ঐ প্রাইমের হাইয়েস্ট পাওয়ার যা n এর  ফ্যাক্টোরিয়াল কে ভাগ করতে পারে। যেমন, 

যদি বর্তমান প্রাইম p হয় তাহলে, n/p^1 + n/p^2 .... n/p^k

এখন যদি n = 4 হয়,

4! = 24
(4/2^1) + (4/2^2)

2 + 1
পরের প্রাইম 3 

(4/3^1)

1

এখন আমরা নিশ্চয়ই জানি, প্রাইমের হাইয়েস্ট পাওয়ার গুলোর সাথে 1 যোগ করে সবগুলো কে গুণ করে দিলেই মোট ডিভিজর সংখ্যা বের হয়ে যাবে। 

(3+1) * (1+1) = 8
24 = 1 2 3 4 6 8 12 24

int mod = 10007; int F_NOD(int n) {   int nod = 1;   for (int i = 0;i < p.size() && p[i] <= n;i++){     int power = p[i];     int freq = 0; /// for store the power of current prime     while (n / power) { /// run until (n / power) becomes zero       freq += n / power;       power = (power * p[i]) % mod;     }     nod = (nod * (freq+1)) % mod;   }   return nod; }

উত্তর যেহেতু অনেক বড় হয়ে যাবে তাই উত্তর int ডাটা টাইপের ভিতরে রাখার জন্যেই উত্তর কে 10007 কে দিয়ে মড করেছি। বাকি কাজ প্রায় NOD বের করার মতই। 

প্র্যাকটিস প্রবলেমঃ
Factors of Factorial

এই বিষয়ে আরো টিউটোরিয়াল। 

টিউটোরিয়াল ১

টিউটোরিয়াল ২