প্রাইম নম্বর হলো এমন একটি নম্বর যা শুধু দুটি সংখ্যা দিয়ে বিভাজ্য: নিজে এবং এক। একটি নম্বরের ফ্যাক্টর হলো সেই নম্বর যা সেটিকে ভাগ করতে পারে।
প্রথম দশ প্রাইম নম্বর: ২, ৩, ৫, ৭, ১১, ১৩, ১৭, ২৩, ২৯, ৩১।
যে নম্বর প্রাইম নয় সেটি কম্পোজিট নম্বর। কম্পোজিট নম্বর হলো এমন নম্বর যা দুটির বেশি নম্বর দিয়ে বিভাজ্য।
প্রাইম এবং কম্পোজিট ছাড়া ১ আছে যা ন तो প্রাইম ন কম্পোজিট কারণ এটি শুধু নিজে দিয়ে বিভাজ্য।
কিভাবে চেক করব একটি নম্বর প্রাইম নাকি কম্পোজিট? একটি নম্বর প্রাইম কিনা চেক করার জন্য দুটি শর্ত পূরণ করতে হয়:
১) এটি ১-র চেয়ে বড় একটি পূর্ণসংখ্যা হতে হবে।
২) এর শুধু দুটি ফ্যাক্টর থাকতে হবে: এক এবং নিজের নম্বর।
যদি এই দুটি শর্ত পূরণ হয়, তবে আমরা বলতে পারি নম্বরটি প্রাইম।
আমাদের প্রোগ্রামে, আমরা নম্বরটিকে সেটির চেয়ে ছোট সব নম্বর দিয়ে ভাগ করব। যদি সেটির চেয়ে ছোট কোনো নম্বর সেটিকে ভাগ করতে পারে, তবে সেটি প্রাইম নম্বর নয়। অন্যথায়, সেটি প্রাইম নম্বর।
দুটি নম্বরের উদাহরণ নেই এবং উপরের প্রসেস দিয়ে চেক করি।
Input − Number1 − 42 Output − 42 is not a prime number
লজিক − ৪২ কে ১-র চেয়ে বড় এবং ৪২-র চেয়ে ছোট সব নম্বর দিয়ে ভাগ করব। তাই,
42/2 = 21 অর্থাৎ ৪২, ২ দিয়ে বিভাজ্য, এর মানে ৪২ প্রাইম নম্বর নয় কারণ এটি অন্য একটি নম্বর দিয়ে বিভাজ্য।
Input − Number2 − 7 Output − 7 is a prime number
লজিক − ৭ কে ১-র চেয়ে বড় এবং ৭-র চেয়ে ছোট সব নম্বর দিয়ে ভাগ করব। তাই,
৭, ২ দিয়ে বিভাজ্য নয়, তাই কোড পরবর্তী নম্বর ৩ চেক করবে।
৭, ৩ দিয়ে বিভাজ্য নয়, তাই কোড ৪ চেক করবে।
৭, ৪ দিয়ে বিভাজ্য নয়, তাই কোড ৫ চেক করবে।
৭, ৫ দিয়ে বিভাজ্য নয়, তাই কোড ৬ চেক করবে।
৭, ৬ দিয়ে বিভাজ্য নয়, এর মানে ৭ শুধু ১ এবং ৭ দিয়ে বিভাজ্য, অর্থাৎ ৭ প্রাইম নম্বর।
উপরের লজিক দেখলে বোঝা যাবে যদি নম্বর ১০০০ বা ১০০০০০ হয়, তবে প্রোগ্রামে उतন ইটারেশন লাগবে। এটি অনেক কম্পিউটেশন টাইম নেবে। তাই ইটারেশন কমাতে একটি ভালো পদ্ধতি আছে।
অপ্টিমাইজড সমাধান হলো লুপকে আধা পথে চালানো। অর্থাৎ যদি নম্বর ৭৭ হয়, তবে লুপ শুধু ৩৮ পর্যন্ত চলবে। এতে ইটারেশন কমে যাবে তাই আমরা এই অ্যালগরিদম ব্যবহার করে প্রোগ্রাম বানাব।
উদাহরণ
#include <stdio.h> int main() { int num = 33, flag = 0; for(int i=2 ; i < num/2 ; i++) { if(num%i == 0) { printf("%d is not a prime number", num); flag = 1; break; } } if(flag == 0) { printf("%d is a prime number", num); } }
আউটপুট
33 is a prime number
