মৌলিক সংখ্যা : সংখ্যার মৌলিকতা পরীক্ষা

ড্রাফট পোস্টঃ


প্রাইম নাম্বার হল তারা যারা কেবল ১ এবং সেই নাম্বার দ্বারা নিঃশেষে বিভাজ্য। সহজ ও সুন্দর সংগা।

কাজেই আসো আমরা একটা নাম্বার প্রাইম কি না তা বের করার যৌক্তিক পদক্ষেপ গুলো নির্ধারণ করি।

ধারনা ১:

আমরা সংখ্যাটিকে প্রথমে ২ দিয়ে ভাগ করা শুরু করতে পারি। এরপর ৩, তারপর ৪, এভাবে সেই সংখ্যাটির আগ পর্যন্ত সকল সংখ্যা দ্বারা ভাগ করে দেখতে পারি যে কোন ভাগ শেষ আসে কি না। যেহেতু ১ দ্বারা সকল সংখ্যা বিভাজ্য এবং যেকোন সংখ্যাই সেই সংখ্যা দ্বারা বিভাজ্য তাই আমরা ২ থেকে শুরু করে সংখ্যাটির আগের সংখ্যা দ্বারা ভাগ করে দেখতে পারি।

কাজেই আমাদের ইনপুট নাম্বার যদি হয় n তাহলে আমরা 2 থেকে শুরু করে n-1 পর্যন্ত ভাগ করব। এই জন্য আমাদের for স্টেটমেন্ট হবে:

for (i =2; i <n;i++)
{
    flag=1;
    if(n%i==0)
    {
        flag=0;
        break;
    }
}

এরপরে আমরা খুব সহজেই flag এর ভ্যালু চেক করে বলতে পারব যে সংখ্যাটি প্রাইম কি না। কারণ আমরা প্রথমেই ধরে নিয়েছি যে flag এর ভ্যালু  ১ এবং সংখ্যাটি i এক কোন মান দ্বারা বিভাজ্য না হলে flag এর মান ১ ই থাকবে।

এই ধারনা দ্বারা ১ থেকে ৩৫০০০০ এর মধ্যেকার সকল প্রাইম নাম্বার (২৯৯৭৭ টি) বের করতে সময় লেগেছে ১১.৮৬ সেকেন্ড। (সময় নির্ধারণঃ ideone)

ধারণা ২:

আমরা ধারণা ১ কে একটু ঘষামাজা করি।
১০/১০=১, ১০/৫=২;
৮/৮= ১, ৮/৪=২;
..........................
n/n =1, n/(n/2)=2;

তাই কোন সংখ্যা তার অর্ধেকের বেশি মানের কোন সংখ্যা দ্বারা নিঃশেষে বিভাজ্য হতে পারে না।

তাই সেই সংখ্যার অর্ধেকের বেশি মানের কোন সংখ্যা দ্বারা তাকে ভাগ করা অর্থহীন।

কাজেই আমরা ২ দ্বারা ভাগ করা শুরু করব এবং সংখ্যাটির অর্ধেক মানের সংখ্যা দ্বারা ভাগ করেই থেমে যাবো। আমাদের for স্টেটমেন্ট হবে:

for(i =2; i <=n/2; i++)
{
    flag =1;
    if(n%i==0)
    {
        flag=0;
        break;
    }
}

ধারণা ২ তে আমাদের ভাগের কাজ হবে ধারণা ১ এর প্রায় অর্ধেক। এই যুক্তি ব্যবহার করে ১-৩৫০০০০ এর মধ্যেকার সব প্রাইম নাম্বার (২৯৯৭৭ টি) বের করতে সময় লেগেছে ৫.৯৪ সেকেন্ড। (সময় নির্ধারণঃ ideone)

ধারণা ৩:

আমরা ধারনা ২ কে আরো একটু স্লিম করার চেষ্টা করি। কেমন?

* সংগা অনুসারে ২ বাদে আর কোন জোড় প্রাইম নাম্বার থাকা সম্ভব না।
* একটি জোড় সংখ্যা সব সময়ই ২ দ্বারা বিভাজ্য
* একটি জোড় ও একটি বিজোড় সংখ্যার গুনফল সব সময়ই একটি জোড় সংখ্যা।

কাজেই কোন সংখ্যা যদি ২ দ্বারা বিভাজ্য না হয় তাহলে তাকে কোন জোড় সংখ্যা দ্বারা ভাগ করে দেখা অর্থহীন।

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

কাজেই আমাদের লজিক হবে:


flag=1;
if (n==2)
    flag=1;
else if (n%2==0)
    flag=0;
else
    for (i = 3; i <=n/2; i += 2)
    {
        if(n%i==0)
        {
            flag=0;
            break;
        }
    }

ধারণা ৩ এ ভাগের কাজ হবে ধারণা ২ এর অর্ধেক। এই ধারনা ব্যবহার করে ১-৩৫০০০০ পর্যন্ত সব প্রাইম নাম্বার (২৯৯৭৭ টি) বের করতে সময় লেগেছে ২.৯৮ সেকেন্ড। (সময় নির্ধারণঃ ideone)

ধারণা ৪:

ইউক্লিড এর প্রস্তাবনা অনুসারে, যে কোন পূর্ণসংখ্যা হয় প্রাইম অথবা তার থেকে ছোট দুই বা ততোধিক প্রাইমের গুণফল। অর্থাৎ, যেকোন সংখ্যা তার চেয়ে ছোট একটি প্রাইম দ্বারা বিভাজ্য হবে যদি সেটি নিজে প্রাইম না হয়।

এখন একটা মজার জিনিস দেখি। ধরা যাক, ১০০ সংখ্যাটি প্রাইম কি না তা আমরা বের করবো। কাজেই ১০০ থেকে ছোট কোন প্রাইম দ্বারা যদি এটি বিভাজ্য না হয় তাহলেই এটি প্রাইম হবে। সবচে ছোট প্রাইম ২। ১০০/২=৫০। ৫০ এর কাছাকাছি প্রাইম হচ্ছে ৪৭। তাই ২ থেকে ৪৭ পর্যন্ত সংখ্যা দ্বারা যদি ১০০ বিভাজ্য না হয় তাহলেই ১০০ প্রাইম।

মজার জিনিসটা হচ্ছে, কোন সংখ্যা যদি প্রাইম না হয় তবে তা তার বর্গমূলের সমান বা তার চেয়ে ছোট কোন না কোন প্রাইম দ্বারা বিভাজ্য। আলোচ্চ্য ১০০ এর ক্ষেত্রে, ১০০ এর বর্গমূল ১০। তাই ২ থেকে ১০ এর মধ্যে কোন সংখ্যা দ্বারা যদি এটি বিভাজ্য না হয় তাহলেই এটি প্রাইম।

১০০ এর কাছাকাছি প্রাইমটি হচ্ছে ৯৭। ২, ৩, ৫, ৭  এই চারটি প্রাইমের কোনটি দ্বারাই ৯৭ বিভাজ্য নয়।

কাজেই,
আমরা যদি কোন সংখ্যার বর্গমূল বের করি এবং ২ থেকে শুরু করে সেই বর্গমূল পর্যন্ত সবগুলো সংখ্যা দিয়ে প্রদত্ত সংখ্যাটিকে ভাগ করে দেখি যে ভাগশেষ শূন্য নয়, তবেই সেটি প্রাইম নম্বর।

আমরা এখন ধারণা ৩ এর সাথে এই ধারণাটা যুক্ত করবো।

অর্থাৎ,


if (n==2)
    flag=1;
else if (n%2==0)
    flag=0;
else
{
    flag=1;
    m= (int) sqrt( (double) n);
    for (i = 3; i <=m; i+=2)
    {
        if (n%i==0)
        {
            flag=0;
            break;
        }
    }
}

এখন flag এর ভ্যালু চেক করলেই বোঝা যাবে যে n প্রাইম কি না।

এই ক্ষেত্রে সময় ধারনা ৩ এর চেয়েও কম লাগবে। এবং সেই কমটাও অনেক অনেক কম।

ধারণা ৪ ব্যবহার করে ১-৩৫০০০০ পর্যন্ত সবগুলো প্রাইম (২৯৯৭৭ টি) বের করতে সময় লেগেছে ০.০২ সেকেন্ড। (সময় নির্ধারণঃ ideone)

কারো ইচ্ছা থাকলে এই ধারণা ৪ টি ব্যবহার করে ১০০০০০ পর্যন্ত যতগুলো প্রাইম নম্বর আছে তা বের করে দেখতে পারো যে কোন ধারণায় কতটা সময় লাগে আউটপুট আসতে।