আমরা জানি ১ থেকে বড় যে সকল সংখ্যার ১ এবং ওই সংখ্যা ছাড়া অন্য কোনো উৎপাদক (divisor) নেই তাদেরকে মৌলিক সংখ্যা বলে । এক্ষেত্রে একটি বিষয় লক্ষণীয় যে ১ মৌলিক সংখ্যা নয়।
এখন যদি বলা কোনো একটি সংখ্যা n মৌলিক কিনা যাচাই করার জন্য , তাহলে উপরের সংজ্ঞা অনুসারে আমরা যেটা করব যে ১ থেকে n সীমার মধ্যে ১ এবং n ছাড়া অন্য কোনো সংখ্যা দিয়ে n নিঃশেষে বিভাজ্য যায় কিনা । অর্থাৎ check করতে হবে যে n % i == 0 কিনা, যেখানে 2<= i <=n-1.
এখানে ২ থেকে n-1 কেন নিলাম? কারণ সব সংখ্যাই ১ এবং ওই সংখ্যা দ্বারা নিঃশেষে বিভাজ্য যায়।
bool Check_if_Prime (int n) {
if(n<=1)return false;
for(int i=2; i<n; i++){
if(n % i == 0){
return false;
}
}
return true;
}
উপরের function টি যখন n এর জন্য call করা হবে , তখন function এর ভিতরের for loop টি ২ থেকে n-1 পর্যন্ত ঘুরবে এবং loop variable i এর প্রতিটি মানের জন্য n % i == 0 কিনা যাচাই করবে। যদি i এর কোনো মানের জন্য n % i == 0 হয়, এর মানে দাঁড়ায় ১ এবং n ছাড়াও n এর অন্য কোনো উৎপাদক আছে । তখন function টি false return করে এর কাজ সমাপ্ত করবে। অন্যথায় পুরো loop ঘুরেও যদি i এর কোন মানের জন্য n % i == 0 না হয় তবে true return করবে। তাহলে function টির time complexity দাঁড়ায় O(n-2) বা O(n) ( যেহেতু complexity হিসাব করার সময় constant value বাদ দেওয়া যায় ) ।
এখন আমরা function টির time complexity কমানোর চেষ্টা করি । প্রথমত খেয়াল করি , যদি ২ দ্বারা n নিঃশেষে বিভাজ্য না হয় তবে n অন্য কোন জোড় সংখ্যা দ্বারাই নিঃশেষে বিভাজ্য হবে না। তাহলে আমাদের function নিচের মতো হতে পারে :
bool Check_if_Prime (int n) {
if(n<=1)return false;
if(n % 2 == 0 && n>2){
return false;
}
for(int i=3; i<n; i+=2){
if(n % i == 0){
return false;
}
}
return true;
}
এক্ষেত্রে আমরা ২ ছাড়া অন্য কোন জোড় সংখ্যার জন্য n এর বিভাজ্যতা যাচাই করিনি । তাহলে আমাদের Check_if_Prime() function এর time complexity হল O(n/2) বা O(n) ( যেহেতু complexity হিসাব করার সময় constant value বাদ দিবো ) . অর্থাৎ কিছুটা optimization হলেও তাত্ত্বিক হিসাবে কোন পার্থক্য হয়নি ।
এখন খেয়াল করি একটি সংখ্যা n এর উৎপাদক বা গুণনীয়ক যদি a হয় তবে (n/a) ও হবে n এর একটি গুণনীয়ক ।
ধরি b = n/a , যেখানে a হচ্ছে n এর একটি উৎপাদক ।
এখন , n = √n * √n
আবার, n = a * b
যদি a < √n হয় , তবে b কে অবশ্যই √n থেকে বড় হতে হবে ।
আবার যদি a < √n হয় , তবে b কে অবশ্যই √n থেকে ছোট হতে হবে ।
আর যদি a = √n হয় , তবে b অবশ্যই √n এর সমান হবে ।
তাহলে আমরা দেখতে পাচ্ছি যে (a,b) জোড়ায় a ও b এর মধ্যে যেকোনো একটি অবশ্যই √n এর সমান অথবা ছোট হবে । একটি উদাহরণ দিলে বিষয়টি আরও স্পষ্ট হবে । আমরা 24 এর উৎপাদকগুলোর দিকে তাকাই :
24 = 1 * 24
= 2 * 12
= 3 * 8
= 4 * 6
আমরা দেখতে পাচ্ছি যে , 24 এর উৎপাদক জোড়াগুলোর মধ্যে সকল জোড়াতেই একটি উৎপাদক √24 এর চেয়ে ছোট বা সমান এই শর্ত মানে।
তাহলে কোন সংখ্যা মৌলিক না হয়ে যৌগিক (composite) হলে এর অবশ্যই 2 থেকে √n সীমার মাঝে কোন না কোন উৎপাদক থাকবে। সুতরাং , Check_if_Prime() function এর ভিতরের loop টি √n পর্যন্ত ঘুরালেই আমদের Prime Checking এর কাজটা হয়ে যাচ্ছে ।
bool Check_if_Prime (int n) {
if(n % 2 == 0 && n>2){
return false;
}
for(int i=3; i*i<=n; i+=2){
if(n % i == 0){
return false;
}
}
return true;
}
উপরের code snippet টি একটু খেয়াল করলেই আমরা দেখব যে , loop এর ভিতর আমরা condition হিসেবে i <= sqrt(n) ব্যবহার না করে i*i<=n করেছি । এর কারণ হচ্ছে sqrt(n) ব্যবহার করলে অনেক সময় double এর precision এ ঝামেলা করে। যেমন sqrt(9) এর জন্য 3 না এসে 2.9999…. আসতে পারে । তখন 2.9999…. কে integer এ রুপান্তর করলে সেটা 3 না হয়ে 2 হয়ে যাবে । তখন 9 কে মৌলিক সংখ্যা হিসেবে দেখাবে ।
তাহলে এখন আমাদের Check_if_Prime() function এর time complexity দাঁড়ালো O(√n).এখন এই বিষয়ক একটি Online judge problem (URI 1165) দেখা যাক।
URI 1165
Problem Link : ( https://www.urionlinejudge.com.br/judge/en/problems/view/1165 )
এই problem এ আমাদেরকে কিছু ইনপুট x এর জন্য , x prime number কিনা তা যাচাই করতে বলেছে। খুব সহজেই আমরা উপরে Check_if_Prime() function টি ব্যবহার করে x prime কিনা তা বলে দিতে পারি। নিচে এর সমাধান দেওয়া হল :
URI 1165 Solution
অনেক বড় কোন একটি সংখ্যা মৌলিক কিনা তা যাচাই করার জন্য আমরা JAVA তে BigInteger.isProbablePrime(int certainty) method টি ব্যবহার করতে পারি। এক্ষেত্রে পরীক্ষাধীন BigInteger টি যদি মৌলিক-সম্ভাব্য হয় তবে method টি true return করবে , আর যদি যৌগিক হয় তবে false rerturn করবে।
এই সম্পর্কিত একটি problem হল Codeforces 1033B - Square Difference . (Link : https://codeforces.com/contest/1033/problem/B)
Codeforces 1033B - Square Difference
এই problem এ আমাদের কিছু test case দেওয়া থাকবে । প্রতিটি test case এ দুটি করে সংখ্যা a ও b দেওয়া থাকবে। আমাদের বলতে হবে (a2 - b2) মৌলিক কিনা । আমরা খুব সহজে JAVA তে (a2 - b2) এর জন্য BigInteger.isProbablePrime(int certainty) method এর return value যাচাই করে বলে দিতে পারি (a2 - b2) মৌলিক কিনা । নিম্নে এর সমাধান দেওয়া হল :
Codeforces 1033B - Square Difference Solution
উপরের এই problem টি আমরা চাইলে গণিত দিয়ে আরও সহজে করতে পারি। এখানে (a2 - b2) কে আমরা লিখতে পারি (a+b) * (a-b) আকারে। এখন (a2 - b2) সংখ্যাটি মৌলিক হবে যদি ও কেবল যদি (a+b) ও (a-b) এর যেকোনো একটি মৌলিক হয় এবং অপরটি 1 হয়। যেহেতু a আর b কোনটিই 1 থেকে ছোট নয় , তাই (a+b) অবশ্যই 1 থেকে বড় হবে । অর্থাৎ (a2 - b2) সংখ্যাটিকে মৌলিক হতে হলে (a-b) কে অবশ্যই 1 হতে হবে এবং (a+b) কে অবশ্যই মৌলিক হতে হবে । তাহলে Check_if_Prime() funtion দিয়ে (a+b) মৌলিক কিনা এবং (a-b) যৌগিক কিনা এতটুকু যাচাই করাই যথেষ্ট হবে । নিচে সমাধান দেওয়া হল:
Codeforces 1033B - Square Difference Solution
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন