আমাদের একটি অ্যারে দেওয়া আছে যাতে প্রাইম ও নন-প্রাইম সংখ্যা র্যান্ডম অর্ডারে আছে। অ্যারের আকার N। লক্ষ্য হল অ্যারেতে সান্মুখ্য প্রাইম সংখ্যার সবচেয়ে দীর্ঘ শৃঙ্খলা খুঁজে বের করা।
প্রাইম সংখ্যা হল যেটির শুধু দুটি ফ্যাক্টর থাকে, ১ এবং নিজের সংখ্যাটি। ১,২,৩,৫,৭,১১,১৩... প্রাইম সংখ্যা যেখানে ৪,৬,৮,৯,১০...২০ নন-প্রাইম। প্রতিটি নন-প্রাইম সংখ্যার ২টির বেশি ফ্যাক্টর থাকে। উদাহরণ দিয়ে বুঝি।
উদাহরণ দিয়ে বোঝা যাক
ইনপুট - Arr[] = { 1,3,5,2,6,7,13,4,9,10
আউটপুট - ৩
ব্যাখ্যা - উপরের অ্যারেতে প্রাইম সংখ্যাগুলো হল 3,5,2,7,13। যেসব সংখ্যা সান্মুখ্য সেগুলো হল 3,5,2 এবং 7,13। সবচেয়ে দীর্ঘ শৃঙ্খলাতে ৩টি সংখ্যা আছে। তাই উত্তর ৩। (মূল টেক্সটে ৪ লেখা আছে যা ভুল।)
ইনপুট - Arr[] = { 5,7,17,27,31,21,41 }
আউটপুট - ৩
ব্যাখ্যা - উপরের অ্যারেতে প্রাইম সংখ্যাগুলো হল 5,7,17,31,41। সান্মুখ্য সংখ্যাগুলো হল 5,7,17। সবচেয়ে দীর্ঘ শৃঙ্খলাতে ৩টি সংখ্যা। তাই উত্তর ৩।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
ইন্টিজার অ্যারে Arr[] ব্যবহার করা হয়েছে প্রাইম ও নন-প্রাইম সংখ্যা সংরক্ষণের জন্য।
isprime(int num) ফাংশন ব্যবহার করা হয়েছে num প্রাইম কিনা চেক করার জন্য। যদি প্রাইম হয় তবে এর অর্ধেক পর্যন্ত কোনো ফ্যাক্টর থাকবে না।
প্রাইম সংখ্যার জন্য isprime() ১ ফেরত দেয় অন্যথায় ০।
primeSubarray(int arr[], int n) ফাংশন দুটি ইনপুট নেয়। অ্যারেটা এবং এর আকার। ফেরত দেয় সান্মুখ্য প্রাইম সংখ্যার সর্বোচ্চ শৃঙ্খলার আকার।
arr[]-এর সংখ্যাগুলো শুরু থেকে ট্রাভার্স করুন। যদি arr[i] নন-প্রাইম হয় (isprime(arr[i])==0) তবে সান্মুখ্য প্রাইম সংখ্যার কাউন্ট ০ করুন।
যদি প্রাইম হয় তবে প্রাইম সংখ্যার কাউন্ট বাড়ান। (নন-প্রাইম পাওয়া গেলে আবার ০ থেকে শুরু হবে)
চেক করুন কাউন্টটি এখনো সর্বোচ্চ কিনা, হ্যাঁ হলে তার মান maxC-এ সংরক্ষণ করুন।
ফলাফল হিসেবে maxC ফেরত দিন।
C++ প্রোগ্রাম উদাহরণ
#include <iostream>
#include <stdio.h>
int isprime(int num){
if (num <= 1)
return 0;
for (int i = 2; i <= num/2; i++)
if (num % i == 0)
return 0;
return 1; // উভয় ফেইল হলে num প্রাইম
}
int primeSubarray(int arr[], int n){
int count=0;
int maxSeq=0;
for (int i = 0; i < n; i++) {
// যদি নন-প্রাইম
if (isprime(arr[i]) == 0)
count = 0;
// যদি প্রাইম
else {
count++;
//printf("\n%d",arr[i]); // প্রাইম সংখ্যা সাবসিকোয়েন্স প্রিন্ট
maxSeq = count>maxSeq?count:maxSeq;
}
}
return maxSeq;
}
int main(){
int arr[] = { 8,4,2,1,3,5,7,9 };
int n =8;
printf("Maximum no. of contiguous Prime Numbers in an array: %d",
primeSubarray(arr, n));
return 0;
}
আউটপুট
Maximum no. of contiguous Prime Numbers in an array : 3
