ফ্যাক্টোরিয়াল ফ্যাক্টস(Factorial Facts)-২

 

ফ্যাক্টরিয়াল ফ্যাক্টরস(Factorial Factors):

কোনো একটা নাম্বার এর প্রাইম ফ্যাক্টর গুলো যদি বের করতে হয়, তাহলে আমরা সেই নাম্বার থেকে ছোট যে প্রাইম নাম্বারগুলো(prime number) আছে সেগুলো দিয়ে দিয়ে ভাগ করে করে ঐ নাম্বারটাকে ফ্যাক্টরাইজ করতে পারি। আমরা কিন্তু ছোটোবেলায় একাজটা করেছি, হয়তো অনেকের মনে নেই। যেমন, আমরা ছোটোবেলায় অংক করার সময় যখন গ.সা.গু আর ল.সা.গু বের করতাম, তখনও কিন্তু আমরা প্রথমে ২ টা নাম্বারের প্রাইম ফ্যাক্টরগুলো বের করে নিয়ে তারপর গ.সা.গু. বা ল.সা.গু. বের করতাম। তারমানে, আমরা যদি ৬০ এর প্রাইম ফ্যাক্টরগুলো বের করতে চাই তাহলে পাবো-
৬০= ২*২*৩*৫
এভাবে, প্রতিটা নাম্বারের ফ্যাক্টরগুলো বের করে তারপর আমরা সেখান থেকে কমনগুলো নিয়ে গ.সা.গু বের করতাম। যাই হোক, এখানে কিভাবে একটা নাম্বারকে আমরা ফ্যাক্টরাইজ করতে পারি সেটা নিয়ে বলবো না। কাজটা খুবই সহজ, যারা পারো না কিভাবে করতে হয় তারা আগে অবশ্যই জানে আলম জান ভাইয়ের একটা সুন্দর টিউটরিয়াল আছে prime factorization নিয়ে। আগে এটা শিখে নাও।
উপরের লিংক কাজ না করলে এখানে দেখতে পারো।
তবে অবশ্যই আগে একটা সাধারণ নাম্বারের প্রাইম ফ্যাক্টর কিভাবে বের করে এটা জানতে হবে। তা নাহলে আমি এখন যে ফ্যাক্টরিয়ালের প্রাইম ফ্যাক্টর বের করার কথা বলবো তার সবটাই নেটওয়ার্কের উপর দিয়ে যাবে।
তাহলে এবার কিভাবে ফ্যাক্টরিয়ালের প্রাইম ফ্যাক্টরস বের করা যায় সেটা নিয়ে বকর বকর শুরু করি।
আমরা জানি যে, খুব ছোট নাম্বারের ফ্যাক্টরিয়ালও অনেক বড় সংখ্যা হয়ে যেতে পারে। সুতরাং, আগে ফ্যাক্টরিয়াল বের করে তারপর তাকে প্রাইম দিয়ে ভাগ করে করে আগের বু্দ্ধিতে……………………… নাহ, এটা খুবই বাজে একটা বুদ্ধি। কারণ, অতবড় একটা সংখ্যাকে এভাবে ফ্যাক্টরাইজ করতে গেলে আমাদের মোটামুটি খবরই আছে। তাহলে, কি করা যায়????? কোনো বুদ্ধি????
হুম…… “Always there is a solution”. :)আচ্ছা, আমরা দেখি যে 10! মানে কি?

10!= 1*2*3*4*5*6*7*8*9*10
ঠিক আছে, তাই যদি হয়, তাহলে আমরা একটু বুদ্ধি খাটাই এখানে, এই সংখ্যাগুলোকে আরো একটু ভাঙ্গি, এরকম করে-
10!= 1* 2 * 3 * (2*2) * 5 * (2*3) * 7 * (2*2*2) * (3*3) * (2*5)
বুদ্ধিমান ব্যক্তিবর্গ এতক্ষণে ধরে ফেলার কথা, আমি এখানে কি করেছি। হ্যাঁ, আমি এখানকার নাম্বারগুলোকে ফ্যাক্টর করে তাদের বদলে ফ্যাক্টর গুলো বসিয়েছি। এটার সাথে কিন্ত আগে লেখা (1*2*3*4……) এটার কোনো পার্থক্য নেই। কিন্তু লাভ যেটা হয়েছে সেটা হলো আমি এখন শুধুমাত্র প্রাইম নাম্বারের গুণফল হিসেবে 10! কে দেখাতে পারছি। তারমানে আমরা কিন্তু এরিমধ্যে 10! কে ফ্যাক্টরাইজ করে ফেলেছি।
যদিও 10!= 3628800  বেশ বড় একটা সংখ্যা কিন্তু আমরা খুব সহজেই এটার ফ্যাক্টরগুলো বের করে ফেলেছি। তারমানে এখন 10! এর prime factorization হচ্ছে-
10! = (2*2*2*2*2*2*2*2) * (3*3*3*3) * (5*5) * 7
      = 28 * 34* 52 * 7
এখন এখান থেকে আমরা কয়েকটা গুরুত্বপূর্ণ জিনিস নোট করতে পারি-
১. N! বের করার জন্য N এর চেয়ে বড় প্রাইম আমাদের লাগবে না।
২. আমরা যদি শুধু বের করতে পারি যে, ফ্যাক্টরাইজেশনে এই প্রাইমগুলোর ফ্রিকোয়েন্সি (মানে, প্রাইমগুলো কতগুলো করে আছে) কত তাহলেই আমাদের ফ্যাক্টরাইজেশন করা হয়ে যাবে।
তারমানে, আমাদের N পর্যন্ত প্রাইম গুলো লাগবে আর প্রাইমগুলোর পাওয়ার কত হবে সেটা লাগবে।
আমরা যদি আবার একটু ১০ এর ফ্যাক্টরিয়ালের দিকে তাকাই, প্রথমে আছে  28
আচ্ছা, এটা কিভাবে আসলো একটু দেখি।
10!= 1*2*3*4*5*6*7*8*9*10
10!= 1* 2 * 3 * (2*2) * 5 * (2*3) * 7 * (2*2*2) * (3*3) * (2*5)
এখানে আমরা দেখি কোন নাম্বারগুলো 2 দিয়ে বিভাজ্য বা কোথায় কোথায় আমরা 2 পাবো।
২,৪,৬,৮,১০ এই ৫ জায়গায় আমরা অন্তত একবার করে ২ পাচ্ছি। তারমানে আমরা এখন পর্যন্ত ২ পেলাম (১০/২ ) = ৫ বার।
আবার ২*২=৪ এর কারণে আমরা আরো একবার করে ২ পাচ্ছি- ৪ এবং ৮ এ। তারমানে আরো পেলাম, (১০/৪) = ২ বার। মোট হলো ৫+২=৭।
আবার ২*২*২ = ৮ এর জন্য আরো একবার ২ পাচ্ছি শুধুমাত্র ৮ এ। তারমানে আরো পেলাম, (১০/৮)=১ বার। মোট হলো, ৫+২+১=৮।
আর কোনো ২ আমরা পাচ্ছি না, কারণ ২*২*২*২=১৬ আমাদের নাম্বার ১০ এর চেয়ে বড়। তারমানে এরপরে কোনোটার জন্য আমরা কোনো ২ পাবো না। এখন তাহলে আমরা দেখি যে, 10! এর জন্য আমরা কতগুলো ২ পাবো সেটা আমরা পেয়ে গেছি,৫+২+১=৮, তারমানে 28
একইভাবে আমরা এবার খুব সহজে বলে দিতে পারি আমাদের পরবর্তী প্রাইম ৩ এর পাওয়ার কত হবে, তাই না?
শুধুমাত্র ৩ পাবো আমরা ৩,৬,৯ এ। আর ৩*৩ এর জন্য আরো একবার ৩ পাবো ৯ এ।
তারমানে ৩ এর পাওয়ার হবে, (১০/৩)+(১০/৯)=৩+১=৪
আমরা উপরে আমাদের ফ্যাক্টরাইজেশনের লাইনে দেখবো যে আসলেই আমাদের 34 আছে। তারমানে বাকি প্রাইমগুলো একইভাবে পাওয়া যাবে।
৫ হবে, (১০/৫)=২
৭ হবে, (১০/৭)=১
তারমানে,
10! = 28 * 34 * 52 * 7
তারমানে মোদ্দাকথা দাঁড়ালো যে, কোনো একটা প্রাইমের পাওয়ার পাওয়া যাবে, তার যেই পাওয়ারগুলো N এর চেয়ে ছোটো, তারা কতবার করে N! এ আছে, যেমন,
(১০/২) = ৫ , ২ আছে ৫ বার
(১০/৪) = ২, ৪ আছে ২ বার
(১০/৮) = ১, ৮ আছে ১ বার
২ এর আর কোনো পাওয়ার নেই ১০ এর মধ্যে তারমানে, 10! এ ২ এর পাওয়ার হবে (৫+২+১)=৮
একইভাবে বাকি প্রাইমগুলো বের করে নিলেই আমরা 10! এর prime factorization পেয়ে যাবো।
মজার কথা হচ্ছে, আমরা কিন্তু 10! এর প্রাইম ফ্যাক্টর বের করার সময় একবারো দেখিনি, 10!=? , অথচ আমরা কিন্তু ঠিকই 10! এর prime factorization করে ফেলেছি। 🙂 কি দরকার অত বড় একটা নাম্বারকে ঘাঁটাঘাঁটি করার? বুদ্ধি থাকলে যে উপায় হয় সেটা তো আমরা দেখলামই।
কতটুকু বুঝতে পেরেছো উপরের হাবিজাবি, সেটা বোঝার জন্য, UVA 884 Factorial factors এই প্রবলেমটা সলভ করার চেষ্টা করে দেখতে পারো। 🙂
Coding is fun…………………………
Want to like or share?:
0

Leave a Reply

Your email address will not be published. Required fields are marked *