প্রাইম সংখ্যা


কোন একটি সংখ্যা প্রাইম কিনা তা বের করার জন্য কি করতে হয় ?

ব্যাখ্যা : প্রাইম হল সেইসকল সংখ্যা যাদের অন্য সংখ্যা দিয়ে ভাগ করা যায় না
মানে, ১ এবং সেই সংখ্যা নিজে বাদে অন্য সংখ্যা দিয়ে ভাগ করা যায় না
মানে, প্রাইম হল সেইসব পজিটিভ সংখ্যা যাদের ১ এবং সেই সংখ্যা নিজে বাদে অন্য সংখ্যা দিয়ে ভাগ করা যায় না

তাহলে ১ কি ? প্রাইম নাকি প্রাইম না ?
= প্রাইম না
= একমাত্র জোড় সংখ্যা, যেটা প্রাইম
= প্রাইম না
কোন ঋণাত্নক সংখ্যা প্রাইম হতে পারে না।

এবার আমরা একটি ফাংশন লিখি প্রাইম বের করার,

bool isPrime (int n)
{
        if ( n < 2 )
                return false; // not prime
        for ( int p = 2; p < n; p++ ) {
                if ( n % p == 0 )
                        return false; // not prime
        }
        return true; // prime
}

একটা সংখ্যা নিই, ১২
এটার ডিভিজর (বিভাজক) গুলো কি কি ? , , , , , ১২
যেকোন সংখ্যাই ১ এবং নিজ দিয়ে ভাগ যায়, তাই সেগুলো বাদ দিই।
তাহলে ১২ এর ডিভিজর দাড়াচ্ছে, , , ,
একটা জিনিস, ৬ এর পর ১২র কোন ডিভিজর নেই, থাকা সম্ভবও নয়
তার মানে, (১২ / ) এর চেয়ে বড় কোন সংখ্যা ১২র ডিভিজর হতে পারে না

ফাংশনটা দাড়াচ্ছে,

bool isPrime (int n)
{
        if ( n < 2 )
                return false; // not prime
        for ( int p = 2; p <= n / 2; p++ ) {
                if ( n % p == 0 )
                        return false; // not prime
        }
        return true; // prime
}

আমাদের লুপটা কতবার ঘুরছে ১২র জন্য ?
p = 2, 3, 4, 5, 6
পর্যন্ত

কোন সংখ্যা যদি 4 দিয়ে ভাগ যায় তাহলে সেটি অবশ্যই 2 দিয়ে ভাগ যাবে
কোন সংখ্যা যদি 6 দিয়ে ভাগ যায় তাহলে সেটি অবশ্যই 2 দিয়ে ভাগ যাবে
তার মানে আমরা 4 এবং 6 কে বাদ দিতে পারি
অর্থ্যাৎ, আমরা 2 থেকে বড় যেকোন জোড় সংখ্যাকে বাদ দিতে যাচ্ছি

bool isPrime (int n)
{
        if ( n < 2 )
                return false; // not prime
        if ( n % 2 == 0 )
                return false; // not prime
        for ( int p = 3; p <= n / 2; p += 2 ) {
                if ( n % p == 0 )
                        return false; // not prime
        }
        return true; // prime
}

এবার লুপটা কতবার ঘুরছে ?
P = 3, 5

এবার একটু জটিলতার দিকে যাই,
যেকোন সংখ্যার square root এর মধ্যে তার একটি ডিভিজর (বিভাজক) পাওয়া যাবেই ,
যদি সেই সংখ্যাটি প্রাইম না হয় ।
মানে, আমাদের লুপ n / 2 পর্যন্ত না ঘুরিয়ে square root (n) পর্যন্ত ঘুরালেই হবে।

bool isPrime (int n)
{
        if ( n < 2 )
                return false; // not prime
        if ( n % 2 == 0 )
                return false; // not prime
        for ( int p = 3; p <= sqrt (n); p += 2 ) {
                if ( n % p == 0 )
                        return false; // not prime
        }
        return true; // prime
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s