임의의 순서로 배열된 소수의 배열이 제공됩니다. 배열의 크기는 N입니다. 목표는 배열에서 연속된 소수의 가장 긴 시퀀스를 찾는 것입니다.
소수는 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)은 숫자가 소수인지 여부를 확인하는 데 사용됩니다. 소수인 경우 절반에 도달할 때까지 인수가 없어야 합니다.
-
소수의 경우 isprime()은 1을 반환하고 그렇지 않으면 0을 반환합니다.
-
PrimeSubarray(int arr[], int n) 함수는 두 개의 입력 매개변수를 사용합니다. 숫자 자체의 배열, 크기입니다. 연속된 소수의 가장 긴 시퀀스의 크기를 반환합니다.
-
arr[]의 숫자를 처음부터 순회합니다. arr[i]가 소수가 아닌 경우( isprime(arr[i])==0 ). 그런 다음 인접한 소수의 개수를 0으로 변경합니다.
-
소수인 경우 소수의 개수를 증가시킵니다. (비소수를 만나면 0부터 다시 시작합니다)
-
지금까지 카운트가 최대인지 확인하고, 그렇다면 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