C++ で書かれており、指定された範囲内の接頭辞と素数の数を見つけます。

この記事では、指定された正の整数配列 arr[] で複数の素数プレフィックスの合計を見つけ、範囲クエリを実行する必要がありますL,R、##L は prefixsum[ ] 配列の初期インデックス値 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[ ] を作成し、その先頭に 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 などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ で書かれており、指定された範囲内の接頭辞と素数の数を見つけます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。