เราได้รับอาร์เรย์ของจำนวนเฉพาะที่จัดเรียงแบบสุ่ม ขนาดของอาร์เรย์คือ N เป้าหมายคือการหาลำดับที่ยาวที่สุดของจำนวนเฉพาะที่อยู่ติดกันในอาร์เรย์
จำนวนเฉพาะคือจำนวนที่มีตัวประกอบเพียง 2 ตัว คือ 1 และจำนวนเฉพาะ 1,2,3,5,7,11,13….เป็นจำนวนเฉพาะในขณะที่ 4,6,8,9,10….20 ไม่ใช่จำนวนเฉพาะ จำนวนที่ไม่ใช่เฉพาะทุกตัวมีตัวประกอบมากกว่า 2 ตัว มาทำความเข้าใจกับตัวอย่างกัน
ป้อนข้อมูล − Arr[] ={ 1,3,5,2,6,7,13,4,9,10
ผลผลิต − 3
คำอธิบาย − จำนวนเฉพาะในอาร์เรย์ด้านบนคือ 3,5,2,7,13 ตัวเลขที่ติดกันคือ 3,5,2 และ 7,13 ลำดับที่ยาวที่สุดมี 3 ตัวเลข คำตอบคือ 4.
ป้อนข้อมูล − Arr[] ={ 5,7,17,27,31,21,41 }.
ผลผลิต − 3
คำอธิบาย − จำนวนเฉพาะในอาร์เรย์ด้านบนคือ 5,7,17,31,41 ตัวเลขที่อยู่ติดกันคือ 5,7,17 ลำดับที่ยาวที่สุดมี 3 ตัวเลข คำตอบคือ 3.
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
อาร์เรย์จำนวนเต็ม Arr[] ใช้เพื่อเก็บตัวเลขเฉพาะและไม่ใช่เฉพาะ
-
ฟังก์ชัน isprime(int num) ใช้เพื่อตรวจสอบว่า num เป็นจำนวนเฉพาะหรือไม่ หากเป็นจำนวนเฉพาะก็จะต้องไม่มีตัวประกอบจนกว่าจะถึงครึ่งหนึ่ง
-
สำหรับจำนวนเฉพาะ isprime() คืนค่า 1 มิฉะนั้นจะคืนค่า 0
-
ฟังก์ชัน primeSubarray(int arr[], int n) รับพารามิเตอร์อินพุตสองตัว อาร์เรย์ของตัวเลขขนาดของมันเอง ส่งกลับขนาดของลำดับที่ยาวที่สุดของจำนวนเฉพาะที่อยู่ติดกัน
-
สำรวจตัวเลขใน arr[] ตั้งแต่เริ่มต้น หาก arr[i] ไม่ใช่ไพรม์ ( isprime(arr[i])==0 ) แล้วเปลี่ยนจำนวนเฉพาะที่อยู่ติดกันเป็น 0
-
หากเป็นจำนวนเฉพาะ ให้เพิ่มจำนวนเฉพาะ (จะเริ่มจาก 0 อีกครั้งหากพบ nonprime)
-
ตรวจสอบว่าการนับสูงสุดจนถึงตอนนี้หรือไม่ หากใช่ ให้เก็บค่าไว้ที่ maxC
-
คืนค่า maxC เป็นผลลัพธ์
ตัวอย่าง
#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; //if both failed then num is prime
}
int primeSubarray(int arr[], int n){
int count=0;
int maxSeq=0;
for (int i = 0; i < n; i++) {
// if non-prime
if (isprime(arr[i]) == 0)
count = 0;
//if prime
else {
count++;
//printf("\n%d",arr[i]); print prime number subsequence
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
