প্রাইম নাম্বার - বেসিক (Prime Number - Basic)

Aug 3, 2013

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

প্রাইম নাম্বারকে অনেকভাবে সংজ্ঞায়িত করা যায়। প্রাইম নাম্বার হল সেই সকল ধনাত্মক পূর্ণ সংখ্যা যাদের ঠিক (exactly) ২টি ভাজক (divisor) আছে। অন্য কথায় বললে, প্রাইম নাম্বার হল সেই সকল ধনাত্মক পূর্ণ সংখ্যা যাদের ঠিক (exactly) ১টি প্রকৃত ভাজক (proper divisor) আছে। আরেকভাবে বললে, প্রাইম নাম্বার হল সেই সকল ধনাত্মক পূর্ণ সংখ্যা যাদেরকে 1 এবং ঐ নাম্বার ব্যতীত আর কোন নাম্বার দিয়ে নিঃশেষে ভাগ করা যায় না।

উদাহরণ দেওয়া যাক। 7 একটি প্রাইম নাম্বার। এর ২টি ভাজক আছে, 1 এবং 7। আবার এর ১টি মাত্র প্রকৃত ভাজক আছে, 1। ( প্রকৃত ভাজক বা proper divisor হচ্ছে সেই সকল ভাজক যারা ভাজ্য অপেক্ষা ছোট। ) অন্যভাবে দেখা যাচ্ছে 7 কে 1 এবং 7 বাদে আর কোন সংখ্যা দিয়ে ভাগ করা যায় না। অতএব 7 একটি প্রাইম নাম্বার। সংজ্ঞা থেকে এটি স্পষ্ট হওয়া উচিৎ যে 1 প্রাইম নাম্বার না। কারণ 1 এর ভাজক শুধু মাত্র 1, অর্থাৎ ১টি। কিন্তু প্রাইমের সংজ্ঞা অনুযায়ী ঠিক ঠিক ২টা ভাজক থাকতে হবে, কমও না, বেশিও না।

তাহলে যদি বলা হয় কোন একটি নাম্বার প্রাইম নাকি সেটি বের করতে, সেটি আমরা কয়েকভাবে করতে পারি। আমরা দেখতে পারি, 1 থেকে ঐ নাম্বার পর্যন্ত যত নাম্বার আছে তার মধ্যে কয়টি দিয়ে নিঃশেষে ভাগ করা যায়। যদি ২টি হয় তাহলে প্রাইম, অন্যথায় প্রাইম না। এর জন্য যদি আমরা একটি ফাংশন লেখি তাহলে সেটি এরকম হবে -

int isPrime( int n )
{
    int i, count = 0;
    for( i = 1; i <= n; i++ ) {
        if( n % i == 0 ) count++;
    }
    if( count == 2 ) return 1; // n প্রাইম, তাই true return
    else return 0; // n প্রাইম না, তাই false return
}

এখানে আমরা 1 থেকে n পর্যন্ত লুপ চালাচ্ছি এবং বারবার ভাগ করছি। একটা জিনিস লক্ষ্য করলে দেখা যাবে, এভাবে 1 থেকে n পর্যন্ত লুপ চালিয়ে count বের না করে, 2 থেকে n-1 পর্যন্ত লুপ চালিয়ে যদি এর মাঝের কোন নাম্বার দিয়ে n কে ভাগ করা যায় তাহলে break করে দিলেই হয়ে যায়। আমরা বলতে পারব n প্রাইম না, কারণ মাঝের কোন একটা নাম্বার দিয়ে n কে ভাগ করা গিয়েছে। এতে করে লুপ কিছুক্ষণ কম সময় চলবে আগের চেয়ে। ফলে প্রোগ্রামের এফিসিয়েন্সি বাড়বে। তাহলে ফাংশনটি এমন হবে -

int isPrime( int n )
{
    int i;
    for( i = 2; i < n; i++ ) {
        if( n % i == 0 ) break;
    }
    if( i == n ) return 1; // লুপ break হয়নি, তাই n প্রাইম
    else return 0; // লুপ break হয়েছে, তাই n প্রাইম না
}

লক্ষ্য করলে দেখা যাবে, প্রোগ্রামটিকে আরও এফিসিয়েন্ট করা যায়। আমরা n পর্যন্ত বা n-1 পর্যন্ত লুপ চালিয়ে দেখছি যে ভাগ করা যায় নাকি। এতদূর লুপ চালানোর আসলে কোন প্রয়োজন নেই। কোন একটা নাম্বারকে তার অর্ধেক অপেক্ষা বড় কোন নাম্বার দিয়ে ভাগ করা সম্ভব না। অর্থাৎ i এর মান যখন বাড়তে বাড়তে n/2 এর সমান হবে, এরপর থেকে n অথবা n-1 পর্যন্ত কোন নাম্বার দিয়ে ভাগ করে দেখারই কোন প্রয়োজন নেই। কারণ সেগুলো দিয়ে n নিঃশেষে বিভাজ্য হওয়া সম্ভব না। অতএব আমরা ফাংশনটিকে পরিবর্তন করি -

int isPrime( int n )
{
    int i;
    for( i = 2; i <= n/2; i++ ) {
        if( n % i == 0 ) break;
    }
    if( i == n/2 + 1 ) return 1; // লুপ break হয়নি, তাই n প্রাইম
    else return 0; // লুপ break হয়েছে, তাই n প্রাইম না
}

অর্থাৎ এখন আমরা নাম্বারটি যত তার অর্ধেক পর্যন্ত লুপ চালিয়েই বলে দিতে পারছি নাম্বারটি প্রাইম নাকি প্রাইম না। কিন্তু এতেও আসলে এফিসিয়েন্সি খুব বেশি বাড়ে না। n এর মান যদি 10^8 বা 10 x 10^7 হয় তাহলে লুপ চলবে 5 x 10^7 বার। অর্থাৎ যেখানে এফিসিয়েন্সি বেশি প্রয়োজন, অনেক বড় নাম্বারের ক্ষেত্রে, সেখানেই দেখা যাচ্ছে যে এফিসিয়েন্সির তেমন একটা তারতম্য হয়নি। একে তাহলে আরও এফিসিয়েন্ট করতে হবে। সে জন্য আরেকটু আলোচনা করা যাক।

কোন একটি নাম্বার, ধরা যাক, 64, এর ফ্যাক্টরগুলো দেখা যাক -

1 x 64 = 64
2 x 32 = 64
4 x 16 = 64
8 x  8  = 64

আরেকটি নাম্বার দেখা যাক, 90, এর ফ্যাক্টগুলো হল -

1 x 90 = 90
2 x 45 = 90
3 x 30 = 90
5 x 18 = 90
6 x 15 = 90
9 x 10 = 90

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

একটু যৌক্তিকভাবে দেখলেই এর প্রমাণ পাওয়া যায়। ধরা যাক একটি নাম্বার n = ab যেখানে n, a, b সকলেই পূর্ণসংখ্যা। এখন a যদি √n এর থেকে ছোট হয় তাহলে b কে অবশ্যই √n এর থেকে বড় হতে হবে, অন্যথায় দুটির গুণফল n হওয়া সম্ভব না। একইভাবে b যদি √n এর থেকে ছোট হয় তাহলে a কে অবশ্যই √n এর থেকে বড় হতে হবে। যদি এমনটি না হয় তাহলে কি হতে পারে দেখা যাক।

ধরলাম a এবং b উভয়েই √n এর থেকে ছোট। a < √n, b < √n । তাহলে ab < √n√n বা ab < n, যেটি ঠিক না। কারণ শুরুতেই আমরা ধরে নিয়েছি n = ab। আবার ধরা যাক a এবং b এর উভয়েই √n এর থেকে বড়। a > √n, b > √n । তাহলে ab > √n√n বা ab > n, এটিও অসম্ভব। অতএব, একটি ফ্যাক্টর যদি √n এর থেকে ছোট হয় অন্যটিকে বড় হতেই হবে। তাহলে আমরা কোন নাম্বার n প্রাইম নাকি পরীক্ষা করার জন্য √n পর্যন্ত নাম্বারগুলো দিয়ে ভাগ করে দেখলেই হয়ে যাচ্ছে। শুধু শুধু n অথবা n-1 অথবা n/2 পর্যন্ত পরীক্ষা করার কোন দরকার নেই। তাহলে ফাংশনটি যেমন হবে -

int isPrime( int n )
{
    int i;
    int x = sqrt( n );
    for( i = 2; i <= x; i++ ) {
        if( n % i == 0 ) break;
    }
    if( n > 1 && i == x+1 ) return 1; // লুপ break হয়নি, তাই n প্রাইম
    else return 0; // লুপ break হয়েছে, তাই n প্রাইম না
}

এখন যদি আমরা 10^8 প্রাইম কিনা পরীক্ষা করতে যাই তাহলে দেখা যাবে এর বর্গমূল পর্যন্ত লুপ চালিয়েই আমরা উত্তর পেয়ে যাচ্ছি। অর্থাৎ 10^4 বার লুপ চালাতে হচ্ছে যা কিনা 5 x 10^7 অপেক্ষা অনেক কম! যদি int এর স্থানে long long হয় এবং নাম্বারটি 10^18 হয় তাহলে এই পরিবর্তন আরও অনেক বেশি লক্ষ্যনীয়।

এখন যদি আমাদেরকে n দিয়ে বলা হয় n পর্যন্ত সকল প্রাইম নাম্বার বের করতে তাহলে আমরা সহজেই n পর্যন্ত লুপ চালিয়ে প্রতিবার isPrime() কল করে বের করে ফেলতে পারব। কিন্তু এখানে যে সমস্যাটি হয় তা হল n এর মান অনেক বড় হয়ে গেলে প্রোগ্রামটির রানটাইম অনেক বড় হয়ে যাবে। কারণ n সংখ্যকবার লুপ চলবে, তার ভিতরে প্রতিবার isPrime() কল হলে আরেকটি লুপ চলবে। ফলে এই এলগোরিদমের কমপ্লেক্সিটি হয় O(n^2)। প্রায়োগিক ক্ষেত্রে তাই আরও অনেক এফিসিয়েন্ট এলগোরিদমের প্রয়োজন পড়ে। সেইজন্য প্রাইম নাম্বার জেনারেট করার আরেকটি এলগোরিদম রয়েছে, সিভ অফ এরাটস্থেনিজ (Sieve of Eratosthenes) নামে। এটি নিয়ে পরবর্তি পর্বে আলোচনা করা হয়েছে।

পরবর্তি পর্বঃ প্রাইম নাম্বার - সিভ অফ এরাটস্থেনিজ