Ditulis dalam C++, cari bilangan awalan dan nombor perdana dalam julat tertentu

Dalam artikel ini, kita perlu mencari berbilang jumlah awalan perdana dalam tatasusunan integer positif yang diberikan arr[ ] dan melaksanakan pertanyaan julat L, R , dengan L ialah tatasusunan indeks awalan[ ] nilai arr[L], R ialah bilangan jumlah awalan yang perlu kita cari.

Untuk mengisi tatasusunan jumlah awalan, kami bermula dari indeks L hingga indeks R dan menambah nilai semasa dengan elemen terakhir dalam tatasusunan yang diberikan. Berikut ialah contoh masalah -

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.

Cara untuk mencari penyelesaian

Daripada masalah ini kita boleh katakan kita perlu mencipta prefixsum tatasusunan baharu[ ] dan menambah jumlah awalan dengan menambah elemen tatasusunan sebelumnya dan semasa elemen elemen tatasusunan yang diberikan. Elemen pertama tatasusunan jumlah awalan ialah nilai pada indeks L dalam tatasusunan yang diberikan.

Kita perlu menjalankan gelung dari L ke R, dengan L dan R ialah tatasusunan yang diberikan, kemudian semak elemen tatasusunan prefixsum[ ] dan tambahkan kiraan bagi setiap perdana yang ditemui.

Contoh

#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

Penjelasan kod di atas

Dalam kod ini, kami mencipta prefixsum tatasusunan[ ] dan mengisinya dengan jumlah elemen sebelumnya bagi tatasusunan prefixsum[ ] dan elemen semasa bagi tatasusunan yang diberikan. Selepas itu kami menyemak sama ada semua nombor tatasusunan awalan adalah perdana atau tidak, di sini kami menggunakan algoritma Ayak Eratosthenes untuk menyemak nombor perdana. Akhir sekali, tambahkan kiraan untuk setiap perdana dan paparkan hasilnya.

Kesimpulan

Dalam artikel ini, kami menemui nombor perdana dalam tatasusunan jumlah awalan dengan menggunakan pendekatan naif dan menggunakan Sieve of Eratosthenes. Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Ditulis dalam C++, cari bilangan awalan dan nombor perdana dalam julat tertentu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!