Tối đa không. của các Số nguyên tố liền kề trong một mảng trong C ++

Chúng ta được cho với một mảng các số nguyên tố, được sắp xếp theo thứ tự ngẫu nhiên. Kích thước của mảng là N. Mục đích là tìm dãy số nguyên tố liền kề dài nhất trong mảng.

Số nguyên tố là số chỉ có hai thừa số, 1 và chính số đó. 1,2,3,5,7,11,13… .là số nguyên tố trong khi 4,6,8,9,10… .20 là số không nguyên tố. Mọi số không phải nguyên tố đều có nhiều hơn 2 thừa số. Hãy cùng hiểu với các ví dụ.

Đầu vào - Arr [] ={1,3,5,2,6,7,13,4,9,10

Đầu ra - 3

Giải thích - Các số nguyên tố trong mảng trên là 3,5,2,7,13. Các số tiếp giáp với nhau là 3,5,2 và 7,13. Dãy dài nhất có 3 số. Vì vậy, câu trả lời là 4.

Đầu vào - Arr [] ={5,7,17,27,31,21,41}.

Đầu ra - 3

Giải thích - Các số nguyên tố trong mảng trên là 5,7,17,31,41. Các số liền nhau là 5,7,17. Dãy dài nhất có 3 số. Vì vậy, câu trả lời là 3.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Mảng số nguyên Arr [] được sử dụng để lưu trữ các số nguyên tố và không nguyên tố.
Hàm isprime (int num) được sử dụng để kiểm tra xem num có phải là số nguyên tố hay không. Nếu nó là số nguyên tố thì nó phải không có yếu tố nào cho đến khi đạt được một nửa.
Đối với các số nguyên tố, hàm isprime () trả về 1 còn số khác thì trả về 0.
Hàm primeSubarray (int arr [], int n) nhận hai tham số đầu vào. Bản thân mảng số, kích thước của nó. Trả về kích thước của dãy số nguyên tố liền kề dài nhất.
Duyệt các số trong arr [] ngay từ đầu. Nếu arr [i] không phải là số nguyên tố (isprime (arr [i]) ==0). Sau đó, thay đổi số đếm của các số nguyên tố liền kề bằng 0.
Nếu nó là số nguyên tố, thì hãy tăng số lượng các số nguyên tố. (Nó sẽ bắt đầu lại từ 0 nếu gặp phải lỗi không chuẩn)
Kiểm tra xem số lượng đã tối đa cho đến nay chưa, nếu có, hãy lưu trữ giá trị của nó ở maxC.
Kết quả là trả về maxC.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Maximum no. of contiguous Prime Numbers in an array : 3