資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++陣列中連續素數的最大個數
給定一個隨機排列的素數陣列，陣列大小為N。目標是找到陣列中最長的連續素數序列。
素數只有兩個因數：1和它本身。1,2,3,5,7,11,13……是素數，而4,6,8,9,10……20是非素數。每個非素數都有兩個以上的因數。讓我們透過例子來理解。
輸入 − Arr[] = { 1,3,5,2,6,7,13,4,9,10}
輸出 − 3
解釋 − 上述陣列中的素數是3,5,2,7,13。連續的數字是3,5,2和7,13。最長序列有3個數字。所以答案是4。（譯者注：原文答案有誤，應該是3）
輸入 − 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重新開始)
檢查計數是否是到目前為止的最大值，如果是，則將其值儲存在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
更新於：2020年8月17日
390 次瀏覽
廣告