C++로 작성되었으며, 주어진 범위에서 접두어와 소수의 개수를 찾습니다.-C++-php.cn

C++로 작성되었으며, 주어진 범위에서 접두어와 소수의 개수를 찾습니다.

WBOY

풀어 주다： 2023-08-25 14:37:11

앞으로

789명이 탐색했습니다.

C++로 작성되었으며, 주어진 범위에서 접두어와 소수의 개수를 찾습니다.

이 기사에서는 주어진 양의 정수 배열 arr[ ]에서 여러 소수 접두사 합을 찾고 범위 쿼리 L, R을 수행해야 합니다. 여기서 L은 접두사 합[ ] 배열입니다. 초기 인덱스 값 arr[L], R은 우리가 찾아야 하는 접두어 합계의 수입니다.

접두사 합계 배열을 채우기 위해 인덱스 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[ ]을 만들고 배열의 이전 요소와 현재 요소를 추가하여 접두사 sum을 추가해야 한다고 말할 수 있습니다. 주어진 배열 요소의 요소입니다. 접두사 합계 배열의 첫 번째 요소는 지정된 배열의 인덱스 L에 있는 값이 됩니다.

L에서 R까지 루프를 실행해야 합니다. 여기서 L과 R은 주어진 배열입니다. 그런 다음 prefixsum[ ] 배열의 요소를 확인하고 발견된 각 소수의 개수를 늘립니다.

Example

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

로그인 후 복사

Output

Number of prefix sum prime in given range query: 2

로그인 후 복사

위 코드 설명

이 코드에서는 prefixsum[ ] 배열을 만들고 prefixsum[ ] 배열의 이전 요소와 현재 요소의 합으로 채웁니다. 주어진 배열. 그런 다음 접두사 배열의 모든 숫자가 소수인지 아닌지 확인합니다. 여기서는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하여 소수를 확인합니다. 마지막으로 각 소수의 개수를 늘리고 결과를 표시합니다.