Prime Numbers and Prime checking

প্রাইম নাম্বার কি?
একটি সংখ্যা n কে প্রাইম নাম্বার বলা হয় যদি ঐ সংখ্যাটি 1 এর চেয়ে বড় হয় এবং 1 এবং n ছাড়া আর কোন পজিটিভ নাম্বার দিয়ে বিভাজ্য না হয়।
1 নিজে একটি প্রাইম নাম্বার না।
প্রথম প্রাইম নাম্বারটি হচ্ছে 2. একমাত্র জোড় প্রাইম নাম্বার হচ্ছে 2. কারন বাকীসব জোড় সংখ্যাকে 2 দ্বারা ভাগ করা যায়।
3, 5, 7 হচ্ছে প্রাইম নাম্বার। কারন তাদের 1 এবং নিজেকে দিয়ে ছাড়া আর কোন নাম্বার দিয়ে ভাগ করা যায় না। 4, 6 কিন্তু প্রাইম নাম্বার না। কারন 4 কে 2 দিয়ে আর 6 কে 2 এবং 3 দিয়ে ভাগ করা যায়।

প্রাইম নাম্বারের সর্বমোট সংখ্যা কতো?
প্রাইম নাম্বারের সংখ্যা অসীম। গণিতবিদ Euclid প্রমান করে দেখান যে প্রাইম নাম্বারের সংখ্যা সসীম হতে পারে না।
ধরি, কেউ একজন দাবি করলো Pn সংখ্যক প্রাইম নাম্বার আছে।
এখন সেই Pn সংখ্যক প্রাইম নাম্বারকে গুণ করে সাথে 1 যোগ করি। ধরি নতুন নাম্বারটি হচ্ছে X.

X = P1 * P2 * P3 * ........ * Pn-1 * Pn + 1.


X-1 কে কিন্তু সেই প্রতিটি প্রাইম নাম্বার দিয়ে নিঃশেষে ভাগ করা যাবে। কিন্তু X কে সেই Pn সংখ্যক প্রাইম নাম্বারের কোন নাম্বার দিয়েই নিঃশেষে ভাগ করা যাবে না। ঐ সকল নাম্বার দিয়ে ভাগ করলে ভাগশেষ থাকবে 1. সেক্ষেত্রে X হচ্ছে একটি প্রাইম নাম্বার। সেক্ষেত্রে বলা যায় কেউ কখনো দাবি করতে পারবে না যে প্রাইম নাম্বার সসীম।
এইভাবে গুণ করলে কি সবসময় প্রাইম পাওয়া যাবে?
আমরা 13 পর্যন্ত সকল প্রাইম নাম্বার গুণ করে 1 যোগ করে দেখি তোঃ

2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031

কিন্তু 30031 = 59 * 509. এটি একটি প্রাইম নাম্বার না।
উপরের প্রমাণ করা হয়েছে যে প্রাইম নাম্বার সসীম হতে পারে না। সেটি বলা হয়নি যে প্রথম থেকে সকল প্রাইম গুণ করে 1 যোগ করলে সবসময় প্রাইম নাম্বার পাওয়া যাবে।

Co-Prime কি?
দুই বা ততোধিক নাম্বারের সেট যাদের মধ্যে 1 ছাড়া আর কোন কমন ডিভিজর নেই তাদের Co-Prime বলা হয়।
উদাহরণ স্বরূপ আমরা 21 আর 22 এর দিকে খেয়াল করি। 21 কে 1, 3, 7, 21 দ্বারা নিঃশেষে ভাগ করা যায়। আর 22 কে 1, 2, 11, 22 দ্বারা নিঃশেষে ভাগ করা যায়। এই দুটি নাম্বারের মধ্যে 1 ছাড়া কমন কোন ডিভিজর নেই। তারা Co-Prime নাম্বার।
কিন্তু 21 আর 27 Co-Prime নয়। 21 কে 1, 3, 7, 21 দ্বারা নিঃশেষে ভাগ করা যায়। আর 27 কে 1, 3, 9, 27 দ্বারা নিঃশেষে ভাগ করা যায়। 21 আর 27 এর মধ্যে 1 ব্যতীত আরেকটি কমন ডিভিজর রয়েছে। তা হচ্ছে 3. তাই তারা Co-Prime নয়।

Co-Prime এর কিছু প্রোপার্টিঃ

1 সকল নাম্বারের সাথেই Co-Prime.

সকল প্রাইম নাম্বার পরস্পরের সাথে Co-Prime. কারন কোন প্রাইম নাম্বারের 1 এবং ঐ নাম্বার নিজে ছাড়া আর কোন ডিভিজর নেই।

পাশাপাশি দুটি নাম্বার সবসময় Co-Prime হয়। কারন প্রথম নাম্বারটিকে যে নাম্বার গুলো দিয়ে নিঃশেষে ভাগ করা যাবে পরের নাম্বারটিকে সে নাম্বার দিয়ে নিঃশেষে ভাগ করা যাবে না। কারন সেখানে ভাগশেষ হিসেবে 1 থাকবে।

দুটি Co-Prime নাম্বারের যোগফল তাদের গুণফলের সাথে Co-Prime হবে। 5 এবং 6 এর যোগফল 11 এবং গুণফল 30. এখানে 11 এবং 30 Co-Prime.

আমরা কিভাবে চেক করবো যে একটি নাম্বার প্রাইম কিনা?

যেহেতু প্রাইম নাম্বার 1 এবং ঐ নাম্বার ব্যতীত আর কোন নাম্বার দিয়ে নিঃশেষে বিভাজ্য নয় সেহেতু একটি নাম্বার n এর জন্য 2 থেকে n-1 পর্যন্ত প্রতিটি নাম্বার দিয়ে ভাগ করে দেখতে পারি যে ঐ নাম্বারটি n কে নিঃশেষে ভাগ করে কিনা।

 
bool IsPrime( int n )
{
    for ( int i = 2 ; i < n; i++ )
    {
        if ( n % i == 0 )return false;
    }
    return true;
}



আমরা এইভাবে খুব সহজেই চেক করতে পারি একটি নাম্বার প্রাইম কিনা। যদি কোন নাম্বার দিয়ে নিঃশেষে ভাগ করা যায় তাহলে আমরা false return করে দিচ্ছি।
আমরা কি এই চেক করার প্রসেসকে আরও দ্রুত করতে পারি?
আমরা জানি 2 ব্যতীত কোন জোড় নাম্বার প্রাইম নয়। তাহলে তো প্রথমেই চেক করতে পারি নাম্বারটি জোড় কিনা। তারপর লুপের ভেতর শুধু বিজোড় নাম্বার দিয়ে চেক করলেই চলবে!
আচ্ছা n কে n/2 এর চেয়ে বড় কোন নাম্বার নিঃশেষে ভাগ করতে পারে?
আমরা কিন্তু n-1 পর্যন্ত লুপ না চালিয়ে n এর অর্ধেক লুপ চালিয়ে চেক করলেই পারি!
আমরা কি আরও কম সময়ে চেক করতে পারি একটি নাম্বার প্রাইম কিনা?
হ্যাঁ আমরা পারি।
আমরা 64 এর সবগুলো ডিভিজর বের করি।
64 এর সবগুলো ডিভিজর হচ্ছে 1,2,4,8,16,32,64.
প্রতিটি ডিভিজর এর কিন্তু একটি pair আছে।
1 * 64 = 64
2 * 32 = 64
4 * 16 = 64
8 * 8 = 64
একটু খেয়াল করলেই দেখতে পারবেন প্রতিটি জোড়ার ছোট নাম্বারটি Square Root of 64 এর চেয়ে ছোট অথবা সমান!
আমরা তাহলে 64 এর ডিভিজর চেক করার জন্য Square Root পর্যন্ত লুপ চালালেই পারি! যেকোনো নাম্বার প্রাইম কিনা সেটা বের করার জন্য আমরা Square Root পর্যন্ত লুপ চালিয়ে চেক করলেই পেয়ে যাবো কোন নাম্বার দিয়ে ঐ নাম্বারকে নিঃশেষে ভাগ করা যায় কিনা। কারন প্রতিটি জোড়ার ছোট নাম্বারটি অবশ্যই ঐ নাম্বার এর Square Root এর চেয়ে ছোট অথবা সমান হবে। 64 এর জন্য খেয়াল করে দেখুন। 64 এর square root হচ্ছে 8. আমরা 8 * 8 এর জন্য পাই 64. এখন যদি এর কোন একটি নাম্বার এক বাড়িয়ে দেই, তাহলে 8 * 9 = 72. আমরা পরিষ্কার ভাবে দেখতে পারছি যে নাম্বারটি 64 এর চেয়ে বড়।
নিজে কোড করে ফেলার চেষ্টা করুন।

bool IsPrime( int n )
{
    ///Checking if the number is 2 or an even number
    if ( n == 2 )return true; 
    else if ( n % 2 == 0 )return false;

    ///Checking if the number is divisible by the odd number under square root
    for ( int i = 3 ; i * i <= n; i++ )
    {
        if ( n % i == 0 )return false;
    }
    return true;
}



আশা করি বুঝতে কোন সমস্যা হয়নি।
যেহেতু আপনি এখন প্রাইম চেক করতে পারেন তাহলে নিচের প্রবলেম গুলো ঝটপট সমাধান করে ফেলুন!

Practice Problems:
10235 - Simply Emirp (Uva) Online Judge.
10924 - Prime Words (Uva) Online Judge.
Noldbach problem - Codeforces.