মঙ্গলবার, ২৩ ফেব্রুয়ারী, ২০২১

Prime Number Checking

 আমরা জানি ১ থেকে বড় যে সকল সংখ্যার ১ এবং ওই সংখ্যা ছাড়া অন্য কোনো উৎপাদক (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

#include <bits/stdc++.h>

using namespace std;

bool Check_if_Prime (int n) {

if(n<=1)return false;

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;

}

int main() {

    int t;

    cin>>t;

    for(int i=0;i<t;i++){

        int x;

        cin>>x;

        if(Check_if_Prime (x)){

            cout<<x<<" eh primo\n";

        }

        else{

            cout<<x<<" nao eh primo\n";

        }

    }

    return 0;

}



অনেক বড় কোন একটি সংখ্যা মৌলিক কিনা তা যাচাই করার জন্য আমরা 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

import java.util.*;
import java.math.*;

public class Main{
    public static void main(String[] args){
        int t;
        Scanner src = new Scanner(System.in);
        t = src.nextInt();
        for(int i=0;i<t;i++){
            BigInteger a,b;
            a=src.nextBigInteger();
            b=src.nextBigInteger();
           
            if((a.multiply(a).subtract(b.multiply(b))).isProbablePrime(10)){
                System.out.println("YES");
            }
            else{
                System.out.println("NO");
            }
        }
    }
}



উপরের এই 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


#include<bits/stdc++.h>


using namespace std;


bool Check_if_Prime (unsigned long long n) {

    if(n<=1ULL)return false;

    if(n % 2ULL == 0 && n>2ULL){

        return false;

    }

    for(unsigned long long i=3; i*i<=n; i+=2ULL){

        if(n % i == 0){

    return false;

        }

    }

    return true;

}

int main(){

    int t;

    cin>>t;

    for(int i=0;i<t;i++){

         unsigned long long a ,b;

         cin>>a>>b;

         if(Check_if_Prime(a+b) && a-b==1){


            cout<<"YES\n";

         }

         else{

            cout<<"NO\n";

         }

    }

}






কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন