মৌলিক সংখ্যা
মৌলিক সংখ্যা (prime number) নিয়েই আজকের লিখা, তাই প্রথমেই জেনে নিই যে মৌলিক সংখা কি?
মৌলিক সংখ্যা কাকে বলে?
মৌলিক সংখ্যা হলো এমন একটি প্রকৃত সংখ্যা ( ২ থেকে শুরু ) যা শধু ১ অথবা ওই সংখ্যাদিয়েই নিঃশেষে ভাগ যায়। প্রথম এবং একমাত্র জোড় মৌলিক সংখ্যা হলো ২। পরবর্তি মৌলিক সংখ্যা গুলো হলো ৩,৫,৭,১১,১৩,১৭,১৯,… । অসীম সংখ্যক মৌলিক সংখ্যা আছে। ০-১০০ এর মধ্যে ২৫ টি, ০-১০০০ এর ১৬৮ টি, ০-১০০০০ এর মধ্যে ১২২৯ টি মৌলিক সংখ্যা আছে। অনেক বড় মৌলিক সংখ্যার (large prime number) উদাহরণ হলো 1299709, 15485863, 179424673,2147483647, 32416190071, 112272535095293, 48112959837082048697 ইত্যাদি।
The largest known prime number (as of November 2020) is 282,589,933 − 1, a number which has 24,862,048 digits when written in base 10. It was found via a computer volunteered by Patrick Laroche of the Great Internet Mersenne Prime Search (GIMPS) in 2018.
প্রাইম নাম্বার বা মৌলিক সংখ্যা প্রোগ্রামিং প্রতিযোগিতাতে একটি জনপ্রিয় বিষয়। আজকে আমরা প্রাইম নাম্বারের সঙ্গে যুক্ত অ্যালগরিদম নিয়ে আলোচনা করবো।
গণিতের পরিভাষায় ১ এর চেয়ে বড় সেই সকল সংখ্যাকে মৌলিক সংখ্যা বলা হয় যাদের শুধুমাত্র দুইটি উৎপাদক আছে। একটি হল ১ এবং অন্যটি সে নিজে।
মৌলিক সংখ্যা: প্রাইম নাম্বার টেস্ট করা ( Primality test )
প্রাইম নাম্বার টেস্ট (primality test) করার জন্য আমরা যেকোনো সংখ্যা কে সংখ্যাগুলো দিয়ে ভাগ দিবো। এই সমাধানটাই আমাদের মাথায় সবার প্রথমে আসে। এই অ্যালগরিদমটির টাইম কমপ্লেক্সিটি O(N)। যা আসলে সবচেয়ে ভালো সমাধান নয়। আমরা আরও দ্রুত সংখ্যাটি মৌলিক কিনা টেস্ট করতে পারি।
আরেকটু ভালো অ্যালগরিদম, টাইম কমপ্লেক্সিটি
যদি কোন নাম্বার N প্রাইম বা মৌলিক না হয় তবে আমরা একে দুইটা ফ্যাক্টর বা গুণনীয়ক a এবং b তে ভাগ করতে পারি। সুতরাং আমরা বলতে পারি,
এখন এটা দেখানো যাবে যে, a আর b কখনো একসাথে এর চেয়ে বড় হবে না এবং এক সাথে ছোটও হবে না। কারণ যদি a আর b দুইটাই এর চেয়ে বড় হয় তবে, কারন, । সুতরাং এর সকল গুণনীয়ক গুলোর মধ্যে এমন একটি গুণনীয়ক আছে যা এর ছোট অথবা সমান থাকবে। তাই আমরা যদি এর চেয়ে ছোট কোন ডিভিজর বা গুণনীয়ক না পাই তাহলে বলতে পারি N অবশ্যই একটি মৌলিক সংখ্যা।
আসলে আমরা যদি 2 থেকে পর্যন্ত সকল মৌলিক সংখ্যা দিয়ে ভাগ করি কাজ হয়ে যাবে, কিভাবে? একটু ভেবে দেখুন 🙂 । এর কমপ্লেক্সিটি
আরও পরুন প্রাইম কাহিনি – মৌলিক সংখ্যা এর অ্যালগরিদম গুলো
মৌলিক গুণনীয়ক (Prime divisors) বের করার জন্য অপটিমাইজড ডিভিশন অ্যালগরিদম
সংখ্যাতত্ত্ব থেকে জানি, মৌলিক সংখ্যা (prime number) N এর শুধু 1 এবং N বাদে অন্য কোনও গুণনীয়ক নেই। অপর দিকে N যদি কোনও যৌগিক সংখ্যা হয় (Composite number) তবে একে তার সমস্ত মৌলিক গুণনীয়কের গুণফল হিসেবে প্রকাশ করা যাবে, অর্থাৎ মৌলিক সংখ্যাগুলো হলো যৌগিক সংখ্যার বিল্ডিং ব্লক। উদাহরণ সরূপ, পরেরটুকুকে মৌলিক সূচকে ফ্যাক্টরাইজেশন বলে।
কোন সংখ্যার (N) মৌলিক গুণনীয়ক বের করার জন্য আমরা প্রথমে একটি মৌলিক সংখ্যার লিস্ট তৈরি করে পরে দেখতে পারি N কে কোন কোন মৌলিক সংখ্যাদিয়ে ভাগ যায়। যেসব দিয়ে ভাগ যায় ওইগুলোই তার মৌলিক গুণনীয়ক।
তবে আমরা চাইলেই একে আরও দ্রুত করতে পারি।
যেকোনো সংখ্যা N কে আমরা হিসেবে লিখতে পারি। যেখানে হলো N এর একটি মৌলিক গুণনীয়ক, এবং
আমরা যদি N কে তার মৌলিক গুননিয়কদিয়ে ভাগ করার মাধ্যমে কমাতে থাকি তাহলে একসময় পাওয়া যাবে, তার কারণ সকল সংখ্যাকে ১ এবং তার অন্য মৌলিক গুণনীয়কের গুণফল আকারে লিখা যায়। মানে আমরা N কে তার মৌলিক গুণনীয়ক দিয়ে ভাগ করতে থাকবো যতক্ষণ না পর্যন্ত হয়।
আমরা আমাদের অ্যালগরিদমটিতে একবার চোখ বুলিয়ে নিই।
- যতক্ষণ N কে ২ দ্বারা ভাগ করা যাবে ততক্ষণ আমরা N কে ২ দ্বারা ভাগ করে যেতে থাকবো এবং একই সাথে এর মান প্রিন্ট করতে থাকবো। অর্থাৎ
- প্রথম কাজের পর N অবশ্যই বিজোড় সংখ্যা হবে, কারণ ১ নং এ আমরা সব ২ কে উঠিয়ে দিয়েছি (কেটে দিয়েছি)। এখন একটি লুপ চালাবো, থেকে পর্যন্ত (কারণ টা ব্যাখ্যা করছি)। যতক্ষণ i দ্বারা N কে ভাগ যাবে, ততক্ষণ আমরা N কে i দ্বারা ভাগ করে N এর মান আপডেট করতে থাকবো এবং এর মান প্রিন্ট করতে থাকবো। অর্থাৎ ।
- ২ নং ধাপে যদি হয় তবে আমরা N এর মান প্রিন্ট করবো।
অ্যালগরিদমের ব্যাখ্যা
যেহেতু ২ একটি মৌলিক সংখ্যা, তাই প্রথম ধাপে আমাদের সংখ্যা থেকে সকল ২ কে কেটে দিবো। আমাদের সংখ্যাটি যদি হয় তবে, প্রথম ধাপে আমাদের সমস্ত ২ কাটা যাওয়ায় পর তে গিয়ে দাঁড়াবে। পরের ধাপে আমরা ৩ থেকে ভাগ করা শুরু করবো। এ ধাপে আমাদের সমস্ত ৩ কাটা পরে বাকি থাকবে। পরে থেকে এ গিয়ে আমরা N কে ৫ দিয়েও কাটাকাটি করে ফেলবো। সব শেষে N এর মান গিয়ে ১ এ দাঁড়াবে (আহারে বেচারা N, সব খেয়ে দিলাম :'( )।
এখন আসি, আমরা আমাদের লুপকে কেন পর্যন্ত নিলাম? আমাদের কোনও প্রাইম ফ্যাক্টর কি এর থেকে বড় হতে পারে না? অবশ্যই পারে। তবে যেকোনো একটি। কিছুক্ষন আগে আমরা প্রমাণ দেখেছিলাম, যেকোনো সংখ্যা হলে a,b একই সাথে থেকে বড় বা ছোট হতে পারবে না। এখন আমরা ধরি, N এর যেকোনো ২ টি প্রাইম ফাক্টর/ডিভিজর/গুননিয়ক থেকে বড়ো। কিন্তু আমরা জানি, । তাই, যখন তখন যা সম্ভব না। তাই আমাদের শুধু একটি মৌলিক গুণনীয়ক গুণনীয়ক সম্ভব যা থেকে বড় অথবা সমান। এই মৌলিক গুণনীয়কটিকেই আমাদের ৩ নং ধাপ থেকে হেন্ডেল করা হবে।
C++ কোড
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include <bits/stdc++.h> using namespace std; void primeFactors(int n) { // Print the number of 2s that divide n while (n % 2 == 0) { cout << 2 << " "; n = n/2; } // n must be odd at this point. So we can skip // one element (Note i = i +2) for (int i = 3; i <= sqrt(n); i = i + 2) { // While i divides n, print i and divide n while (n % i == 0) { cout << i << " "; n = n/i; } } // This condition is to handle the case when n // is a prime number greater than 2 if (n > 2) cout << n << " "; } int main() { int n = 315; primeFactors(n); return 0; } |
মৌলিক সংখ্যার অ্যালগরিদম: কোনও সংখ্যা (N) এর গুণনীয়কের সংখ্যা বের করা।
এরকম সমস্যা, Given a number N, find the number of divisors (NOD) it has বা একটি সংখ্যা N দেয়া আছে, এর কতগুলো গুণনীয়ক আছে তা বের করুন, প্রোগ্রামিং কনটেস্টগুলোতে প্রায়ই দেখা যায়। এই সমস্যাটির একটি সমাধান হতে পারে, ১ থেকে শুরু করে N পর্যন্ত সকল সংখ্যা দিয়ে N কে ভাগ করে যাবো। যেসব সংখ্যা দিয়ে ভাগ করার পরে ভাগশেষ শূন্য হবে, ওইগুলোই হবে তার গুণনীয়ক। কোডটি দেখলে নিচের মতো হবে,
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include<bits/stdc++.h> using namespace std; int main() { int n,num_divisors=0; cin>>n; for(int i=1;i<=n;++i){ if(n%i==0){ ++num_divisors; } } cout<<"Number of divisors = "<<num_divisors<<endl; return 0; } |
এই কোডের টাইম কমপ্লেক্সিটি হলো । কিন্তু আমরা এই সমস্যাটিকে এ সমাধান করতে পারি। কিভবে?
উপরে আমরা একটি সংখ্যাকে মৌলিক গুণনীয়কে বিশ্লেষণ করেছি। আমরা আমাদের ওই মৌলিক গুণনীয়কগুলোকেই ব্যাবহার করবো ওই সমস্যা সমাধান করতে।
ধরা যাক, কোন সংখ্যা , এখানে হলো N এর একটি মৌলিক গুণনীয়ক। এখন চিন্তা করে দেখি, যেকোনো সংখ্যা, কে যদি N এর গুণনীয়ক হতে হয় তবে এর মধ্যে কি কি বৈশিষ্ট্য থাকা জরুরি। (১) এর মধ্যে N এর মৌলিক গুণনীয়ক ছাড়া অন্যকিছু থাকা চলবে না। (২) এর মধ্যে এর ঘাত N এর মধ্যে এর ঘাত থেকে বেশি হতে পারবে না। অর্থাৎ যেখানে । আমাদের NOD এর সূত্র হলো,
এই সূত্রটি এমন কেন হলো? কারণ হলো কোন ডিভিজর d এর ভিতরে প্রাইম নাম্বার এর ঘাত 0 থেকে যেকোনোটি হতে পারে। অর্থাৎ রকম। এভাবে প্রতিটি ঘাত কতরকম হতে পারে তা গুন করলেই আমরা মোট কতগুলি উৎপাদক/ডিভিজর আছে তা বের করতে পারি। কোডটি দেখি,
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include<bits/stdc++.h> using namespace std; int main() { int n,num_divisors=1; cin>>n; for(int i=2;i*i<=n;++i){ int power=0; while(n%i==0){ ++power; n/=i; } num_divisors=num_divisors*(power+1); } //বর্গমূলের থেকে বড় ফ্যাক্টরের জন্য , আমাদের এরকম ফ্যাক্টর একটিই থাকা সম্ভব, এরকমটি হলে আমরা তাকেও ডিভিজর হিসেবে নেবো। if(n>=2) num_divisors=num_divisors*(1+1); cout<<"Number of divisors = "<<num_divisors<<endl; return 0; } |
কোনও সংখ্যা (N) এর গুণনীয়কের যোগফল বের করা (Finding sum of divisors of a given number N)
কোন সংখ্যা N এর সবগুলো গুণনীয়কের যোগফল (Sum Of Divisor বা SOD) বের করতে বলা হয়েছে, এই সমস্যাটিকেউ আমরা খুব সহজে সমাধান করতে পারি। তার আগে আমরা SOD এর সূত্রটি দেখে নিই।
সূত্রটি ভালভাবে বুঝার জন্য আমরা ধরে নিচ্ছি। তাহলে । অতএব SOD(12) হবে,
বা বা অতএব আমরা আমাদের গুণনীয়কের যোগফল পেয়ে গেলাম। আশাকরি বুঝাগেছে। 1 নং সমীকরণকে আমরা নিচের মতো লিখতে পারি,
SOD বের করার কোড,
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; map <int,int> primes; for(int i=2;i*i<=n;++i){ int power=0; while(n%i==0){ ++power; n/=i; } if(power>0){ primes[i]=power; } } //বর্গমূলের থেকে বড় ফ্যাক্টরের জন্য , আমাদের এরকম ফ্যাক্টর একটিই থাকা সম্ভব, long long sod=1; primes[n]++; for(pair <int,int> k:primes){ int p=k.first; int a=k.second; sod=sod*(pow(p,a+1)-1)/(p-1); } cout<<"Sum of divisors= "<<sod<<endl; return 0; } |
দেখলাম কিভাবে কোন সংখ্যাকে দ্রুত প্রাইম ফ্যাক্টরে ভাগ করতে পারি এবং তা থেকে কিভাবে Number of Divisor এবং Sum of Divisor বের করতে পারি। আগামী লিখায় অন্য কোন টপিকে লিখবো। আজকের মতো যাচ্ছি, ৬ তারিখ ক্লাসের এসাইনমেন্ট জমা দিতে হবে। কারও সমস্যা বা কনফিউশন থাকলে কমেন্ট অথবা মেইলে জানাবেন।
সংখ্যা তত্ত্ব নিয়ে দ্বিতীয় লিখা এখানে সংখ্যাতত্ত্ব: মডুলার অ্যারিথমেটিক (Modular arithmetic) – Big mod
ধন্যবাদ, আশা করি প্রোগ্রামিং কনটেস্টে কাজ এ লাগবে। ভাইয়া, ম্যাপ শেখার বাংলা কোন সোর্স থাকলে দিয়েন।
Well writing🤍.
Thank you. 🤍.