পূর্ণ সংখ্যার প্রাইম ফ্যাক্টরাইজেশন

নাম্বার থিওরীতে কোন একটি ধনাত্মক সংখ্যার মৌলিক গুণনীয়ক বা প্রাইম ফ্যাক্টর হলো এমন কতগুলো মৌলিক সংখ্যা যা ঐ সংখ্যাটিকে সঠিকভাবে ভাগ করে । মানে, যে সকল প্রাইম নাম্বার দিয়ে ঐ সংখ্যাটিকে ভাগ দিলে ভাগশেষ শূন্য হয়, তারাই সংখ্যাটির মৌলিক গুণনীয়ক।

Posted by Rabiul Awal on July 30, 2015

প্রাইম ফ্যাক্টরাইজেশন

নাম্বার থিওরীতে কোন একটি ধনাত্মক সংখ্যার মৌলিক গুণনীয়ক বা প্রাইম ফ্যাক্টর হলো এমন কতগুলো মৌলিক সংখ্যা যা ঐ সংখ্যাটিকে সঠিকভাবে ভাগ করে। মানে, যে সকল প্রাইম নাম্বার দিয়ে ঐ সংখ্যাটিকে ভাগ দিলে ভাগশেষ শূন্য হয়, তারাই সংখ্যাটির মৌলিক গুণনীয়ক। মৌলিক গুণনীয়ক নির্ণয়ের এ প্রক্রিয়াকে বলা হয় – ইন্টিজার ফ্যাক্টরাইজেশন । ফান্ডামেন্টাল এরিথমেটিক থিওরেম অনুযায়ী প্রত্যেকটি ধনাত্মক সংখ্যার একটি সিঙ্গেল এবং ইউনিক প্রাইম ফ্যাক্টরাইজেশন থাকা আবশ্যিক।

প্রাইম ফ্যাক্টরাইজেশনের উদাহরণ –
৩৬০ = ২ * ২ * ২ * ৩ * ৩ * ৫
ফ্যাক্টরগুলো পাওয়ার আকারেও দেখানো সম্ভব ।
৩৬০ = ২^৩ * ৩^২ * ৫
যেসকল ধনাত্মক পূর্ণসংখ্যার কমন প্রাইম ফ্যাক্টর থাকে না তাদেরকে কো-প্রাইম বলা হয়। দুটি সংখ্যার গসাগু-র মান যদি ১ হয়, তাদেরকেও কো-প্রাইম বলা হয়।

এলগরিদম

একটি সংখ্যার(N) প্রাইম ফ্যাক্টরস বের করার ইফিশিয়েন্ট উপায়
১. যতক্ষণ পর্যন্ত $N$ ২ দিয়ে ভাগ যায়, ততক্ষণ ভাগ করা এবং ২ কে প্রাইম ফ্যাক্টর হিসেবে প্রিন্ট করতে হবে ।
২. এই ধাপে এসে $N$ অবশ্যই বিজোড় সংখ্যা হবে । এখন একটি লুপ চালাতে হবে । কাউন্টার $i = 3$ থেকে sqrt(N) পর্যন্ত। যতক্ষণ পর্যন্ত $i$ দ্বারা $N$ বিভাজ্য হয়, ততক্ষণ $i$ কে প্রিন্ট করতে হবে এবং $N$ কে $i$ দ্বারা ভাগ করতে হবে । তারপর কাউন্টার মান ২ বৃদ্ধি করতে হবে । এবং লুপ $sqrt(N)$ পর্যন্ত চলতে থাকবে ।
৩. যদি সংখ্যাটি (N) একটি প্রাইম নাম্বার হয় এবং ২ থেকে বড় হয়, তাহলে উপরের দুই ধাপে N এর মান ১ হবে না। সেক্ষেত্রে $N$ ২ থেকে বড় হলে, $N$ এর মান প্রিন্ট করতে হবে। মানে $N$ নিজেই নিজের প্রাইম ফ্যাক্টর ।

কোড

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