Prime Numbers (sieve of Eratosthenes)

প্রাইম  (Prime ) সংখ্যা বলতে আমরা বুঝি এমন সংখ্যা যাকে ঐ সংখ্যা যার শুধুমাত্র ২ টি ফ্যাক্টর ( ১ এবং সংখ্যাটি নিজে ) আছে। অর্থাৎ যেসব সংখ্যাকে ঐ সংখ্যা এবং ১ ছাড়া আর কোন সংখ্যা দিয়ে ভাগ করা যায়না। যেমনঃ ২, ৩, ৫, ৭,... এগুলো প্রাইম সংখ্যা। আবার ৮ কিন্তু প্রাইম না, কারন ৮ এর ফ্যাক্টর ১, ২, ৪, ৮। প্রাইম ছাড়া যেসব সংখ্যা আছে, তাদেরকে বলা হয় কম্পোজিট (Composite) সংখ্যা।

প্রাইম এবং কম্পোজিট সংখ্যার জ্যামিতিক ব্যাখ্যা

প্রাচীনকালের গনিতবিদরা, বিশেষ করে গ্রীক গনিতবিদরা সবসময় সংখ্যাকে জ্যামিতিক ব্যাখ্যা আকারে উপস্থাপন করার চেষ্টা করতেন।যেমন বর্গ সংখ্যাগুলোকে একই সংখ্যক সারি এবং কলাম আকারে ছোট ছোট পাথরের মাধ্যমে সাজানো হত। প্রথম পাঁচটি বর্গ সংখ্যা ১, ৪, ৯, ১৬, ২৫।
আয়তাকার সংখ্যারাও অনেক জনপ্রিয়। যেমন ধরা যাক, ১২ কে নিম্নোক্ত উপায়ে আয়তাকারভাবে ছোট ছোট পাথর এর মাধ্যমে দেখানো যায়ঃ

 দেখা যাচ্ছে, ১২ কে ৩ রকমভাবে আয়তাকার আকারে সাজানো যায়।
যেসব সংখ্যাকে ১ এর বেশি আয়তাকার আকারে সাজানো যায় না, তাদেরকে প্রাইম সংখ্যা বলে। যেমন, ৩, ৫, ৭ কে শুধু একটিমাত্র সারি তে সাজানো যায়ঃ

কাজেই, জ্যামিতিকভাবে লক্ষ্য করলে আমরা দেখতে পাই যে প্রাইম সংখ্যার শুধুমাত্র ১ এবং ঐ সংখ্যা ছাড়া আর কোন ফ্যাক্টর নেই।

১ কি প্রাইম ?

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

সীভ অফ ইরাটোস্থেনেস(sieve of Eratosthenes)

গ্রীক দার্শনিক এবং গনিতবিদ ইরাটস্থেনেস সবার প্রথম একটি সসীম ধারায় প্রাইম সংখ্যাগুলোকে ব্রুট ফোর্স ( Brute force ) আকারে লিখতে সক্ষম হন।
তার নামানুসারে এইভাবে প্রাইম সংখ্যা বের করার অ্যালগরিদমটির নাম হল sieve of Eratosthenes.  এই অ্যালগরিদমটির মাধ্যমে আমরা ১০ কোটির নিচের সকল প্রাইম সংখ্যা খুব অল্প সময়ের মধ্যে বের করে ফেলতে পারি।
sieve শব্দের অর্থ হল ছাকনি যা অপ্রয়োজনীয় অংশ ছেটে ফেলে।

আমরা এই টেবিলটি খেয়াল করি। ধরি আমার ১ থেকে ১০০ এর মধ্যে কিকি প্রাইম সংখ্যা আছে, তা সীভ অ্যালগো ব্যবহার করে বের করতে হবে। এখন সীভ এর ব্যাপারটা হচ্ছে, শুরু থেকে এক এক করে সকল সংখ্যা দেখতে দেখতে সামনে এগিয়ে যেতে হবে। সামনে আগানোর পথে যখনি আমরা কোন সংখ্যা পাবো যাকে আগে পাইনি, সেটা আমরা কেটে ফেলে দিবো। এখন প্রথমে আমি ১ বাদ দিয়ে ২ থেকে যাত্রা শুরু করবো (১ কেন বাদ দিলাম, তা একটু পরে তোমরা নিজেরাই বুঝে যাবে)। এখন ২ যেহেতু আগে পাইনি তাই ২ প্রাইম হিসেবে মার্ক করে রাখবো, এরপরে আমরা প্রাইম এর একদম বেসিক আইডিয়া থেকে যা জানি, একটা সংখ্যা যদি প্রাইম হয়, তাহলে ঐ সংখ্যার চেয়ে বড় ঐ সংখ্যার সকল গুনিতক কে আমরা প্রাইম থেকে বাদ দিয়ে দিতে পারি। কেননা ঐ বড় সংখ্যাগুলো অবশ্যই ঐ সংখ্যা দিয়ে ভাগ যাবে, ফলে এগুলো প্রাইম হিসেবে নেয়া যাবেনা। যেমন ২ এ আসার পরে আমরা ২ এর পরের ২ এর গুনিতকগুলো যেমন ৪, ৬, ৮, ... এভাবে ১০০ পর্যন্ত সব কেটে দিবো। এরপরে আমরা আবার আগের জায়গায় ফিরে আসি। আগে আমরা ২ এ ছিলাম, এখন আমরা যাবো ৩ এ। যেহেতু ৩ কাটা পড়েনি, তাই ৩ কে প্রাইম হিসেবে মার্ক করবো এবং ৩ এর চেয়ে বড় ৩ এর গুনিতকগুলি কেটে দিবো। এরপরে কাজ শেষে আবার আমরা আসবো ৪ এ। এখন এই ৪ কিন্তু ২ এর সময় কাটা পড়ে গিয়েছিল, কাজেই আমরা ৪ কে বাদ দিয়ে সামনে আগাবো, কারন আমরা জানি, ৪ প্রাইম না। এভাবে করে আগালে আমরা সুন্দরভাবে প্রাইম সংখ্যাগুলি পেয়ে যাবো। আশা করি সবাই এতক্ষণে বুঝে ফেলেছো কেন আমরা ১ থেকে যাত্রা শুরু করিনি। ১ থেকে যদি যাত্রা শুরু করতাম, তাহলে সীভ মেথড অনু্যায়ী ১ কে আমরা প্রাইম হিসেবে মার্ক করতাম, এবং এরপরে ১ এর চেয়ে বড় ১ এর সকল গুনিতক কে কেটে ফেলতাম! তাহলে আর সংখ্যাই তো থাকলো না !! এজন্যে ১ কে প্রাইম হিসেবে ধরা হয়না। অবশ্য কোন কোন জায়গায় ১ কে প্রাইম হিসেবে ধরতেও পারে। আমরা যারা কন্টেস্ট প্রব্লেম সল্ভ করি, প্রশ্নে যদি ১ কে প্রাইম ধরে কাজ করতে বলা হয়, তাহলে তাই করতে হবে, নাহলে আসলে ১ কে প্রাইম ধরা অযৌক্তিক।
আমরা যদি দেখতে চাই, N একটি প্রাইম কিনা, তাহলে আমাদের কি আসলেই N-1 পর্যন্ত সংখ্যা বিবেচনায় আনার দরকার আছে? একটু খেয়াল করলে দেখতে পারবো যে, আমরা যদি N/2 পর্যন্ত সংখ্যা চেক করি, তাহলেই কাজ হয়ে যাচ্ছে। এখন N/2 এর চেয়েও আরো ভাল একটি উপায় হল √N ( square root of N )।

কেন স্কয়ার রুট অফ N ? ( Why square root of N? )

ধরি আমরা 24 এর জন্য চেক করবো সংখ্যাটি প্রাইম কিনা। এরজন্য আমাদের √24 = 4.89897948557 ≅ 4
অর্থাৎ আমাদের মাত্র 4-1=3 টি সংখ্যা চেক করলেই আমরা বলতে পারবো 24 প্রাইম কিনা। এই 3 টি সংখ্যা হবে 2,3,4.
আমরা 1 কে বিবেচনায় রাখিনি, তাই 1 বাদ যাবে। কেন এই স্কয়ার রুট কাজ করে তার জন্য আমরা যদি 24 এর ফ্যাক্টর গুলি বের করি, তাহলে বুঝতে পারবো।

খেয়াল করলে দেখবো যে, 24 এর উৎপাদকগুলির মাঝে আমরা যদি 4 পর্যন্ত চেক করি, তাহলেই সব সংখ্যা চেক করা হয়ে যাচ্ছে।মানে 24 একবার 2 দিয়ে ভাগ গিয়েছে, কাজেই আবার 12 দিয়ে ভাগ দেয়ার কোন দরকার নেই। আর 24 এর স্কয়ার রুট হচ্ছে 4। কাজেই স্কয়ার রুট পর্যন্ত হিসাব করা আমাদের জন্য ভালো অপশন।

সুডোকোডঃ

সীভ অ্যালগরিদম এর টাইম কমপ্লেক্সিটি O ( n log n)।