이 기사에서 우리는 주어진 배열 arr[ ]에서 소수인 접두사 합과 범위 쿼리 L을 찾아야 합니다. , R , 여기서 L prefixsum[ ] 배열 및 R에 대한 초기 인덱스 값 arr[ L ] 찾아야 할 접두사 합계의 수입니다.
접두사 합계 배열을 채우기 위해 인덱스 L부터 인덱스 R까지 시작하여 주어진 배열의 마지막 요소에 현재 값을 추가합니다. 여기 문제의 예가 있습니다 -
Input : arr[ ] = { 3, 5, 6, 2, 4 }
L = 1, R = 3
Output : 3
Explanation : prefixsum[ 0 ] = arr[ L ] = 5
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 2 ] = 11
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 3 ] = 13
In prefixsum[ ] array all three 5, 11 and 13 are prime numbers in prefix sum array in given range.
Input : arr[ ] = { 6, 10, 5, 8, 11 }
L = 0, R = 3
Output : 1
Explanation : prefixsum[ 0 ] = arr[ L ] = 6
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 1 ] = 16
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 2 ] = 21
prefixsum[ 3 ] = prefixsum[ 2 ] + arr[ 3 ] = 29
In prefixsum[ ] array only 29 is the prime number in prefix sum array given range. 해결책을 찾기 위한 접근 방식
문제를 살펴보면 하나의 새로운 배열 prefixsum[ ]을 만들고 prefix sum 배열의 이전 요소와 주어진 배열의 현재 요소를 추가하여 해당 배열을 채워야 한다고 말할 수 있습니다. 접두사 합계 배열의 첫 번째 요소는 지정된 배열의 인덱스 L에 있는 값입니다.
L과 R이 주어진 배열에서 처리할 인덱스 범위인 L에서 R까지 루프를 실행한 다음, prefixsum[ ] 배열의 요소를 확인하고 발견된 모든 소수에 대해 개수를 증가시켜야 합니다.
예시
#include<bits/stdc++.h>
using namespace std;
vector < bool > checkprime (int *arr, int n, int MAX){
vector < bool > p (n);
bool Prime_val[MAX + 1];
for (int i = 2; i < MAX; i++)
Prime_val[i] = true;
Prime_val[1] = false;
for (int p = 2; p * p <= MAX; p++){
// If prime[p] is not changed, then
// it is a prime
if (Prime_val[p] == true){
// Update all multiples of p
for (int i = p * 2; i <= MAX; i += p)
Prime_val[i] = false;
}
}
for (int i = 0; i < n; i++){
if (Prime_val[arr[i]])
p[i] = true;
else
p[i] = false;
}
return p;
}
int main (){
int arr[] = { 2, 3, 4, 7, 9, 10 };
int s1 = sizeof (arr) / sizeof (arr[0]);//size of given array
int L = 1, R = 3, s2 = R - L + 1;
int prefixsum[s2];
int count = 0;
prefixsum[0] = arr[L];
for (int i = L + 1, j = 1; i <= R && j < s1; i++, j++){
prefixsum[j] = prefixsum[j - 1] + arr[i];
}
vector < bool > isprime = checkprime (prefixsum, s2, prefixsum[s2 - 1]);
for (int i = 0; i < s2; i++) {
if (isprime[i] == 1)
count++;
}
cout <<"Number of prefix sum prime in given range query: " << count;
return 0;
} 출력
Number of prefix sum prime in given range query: 2
위 코드 설명
이 코드에서 우리는 배열 prefixsum[ ]을 만들고 prefixsum[ ] 배열의 이전 요소와 주어진 배열의 현재 요소의 합으로 채우고 있습니다. 그 후, 우리는 소수에 대한 접두사 배열의 모든 수를 확인하고 있으며 여기에서는 에라토스테네스의 체 알고리즘을 사용하여 소수를 확인합니다. 마지막으로 각 소수의 개수를 증가시켜 결과를 보여줍니다.
결론
이 기사에서 우리는 순진한 접근 방식을 적용하고 에라토스테네스의 체를 사용하여 주어진 범위 쿼리에서 다수의 접두사 합 소수를 찾는 문제를 해결했습니다. 접두사 합계 배열에서 소수를 찾습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.