Ditulis dalam C++, cari bilangan nombor perdana dalam subarray

Dalam artikel ini, kami akan menerangkan kaedah untuk mencari nombor nombor perdana dalam subarray. Kami mempunyai susunan arr[] nombor positif dan pertanyaan q dengan dua integer mewakili julat kami {l, R} dan kami perlu mencari bilangan nombor perdana dalam julat yang diberikan. Di bawah adalah contoh masalah yang diberikan -

Input : arr[] = {1, 2, 3, 4, 5, 6}, q = 1, L = 0, R = 3

Output : 2

In the given range the primes are {2, 3}.

Input : arr[] = {2, 3, 5, 8 ,12, 11}, q = 1, L = 0, R = 5

Output : 4

In the given range the primes are {2, 3, 5, 11}.

Cara untuk mencari penyelesaian

Dalam kes ini, saya fikirkan dua cara -

#🎜🎜 #brute force

Dalam kaedah ini kita boleh mengambil julat dan mengetahui bilangan nombor perdana yang terdapat dalam julat itu.

Contoh

#include <bits/stdc++.h>
using namespace std;
bool isPrime(int N){
    if (N <= 1)
       return false;
    if (N <= 3)
       return true;
    if(N % 2 == 0 || N % 3 == 0)
       return false;
    for (int i = 5; i * i <= N; i = i + 2){ // as even number can&#39;t be prime so we increment i by 2.
       if (N % i == 0)
           return false; // if N is divisible by any number then it is not prime.
    }
    return true;
}
int main(){
    int N = 6; // size of array.
    int arr[N] = {1, 2, 3, 4, 5, 6};
    int Q = 1;
    while(Q--){
        int L = 0, R = 3;
        int cnt = 0;
        for(int i = L; i <= R; i++){
           if(isPrime(arr[i]))
               cnt++; // counter variable.
        }
        cout << cnt << "\n";
    }
    return 0;
}

Output

2

Namun, kaedah ini tidak begitu baik kerana kerumitan keseluruhan kaedah ini adalah #O(Q*N *√N)

, ini tidak begitu bagus. KAEDAH CEKAP

Dalam kaedah ini kita akan menggunakan Ayak Eratosthenes untuk mencipta tatasusunan boolean yang memberitahu kita sama ada elemen itu adalah perdana dan kemudian lelaran melaluinya Memandangkan julat dan cari jumlah bilangan nombor perdana dalam tatasusunan itu. tatasusunan boolean.

Contoh

#include <bits/stdc++.h>
using namespace std;
vector<bool> sieveOfEratosthenes(int *arr, int n, int MAX){
    vector<bool> p(n);
    bool Prime[MAX + 1];
    for(int i = 2; i < MAX; i++)
       Prime[i] = true;
    Prime[1] = false;
    for (int p = 2; p * p <= MAX; p++) {
       // If prime[p] is not changed, then
       // it is a prime
       if (Prime[p] == true) {
           // Update all multiples of p
           for (int i = p * 2; i <= MAX; i += p)
               Prime[i] = false;
       }
    }
    for(int i = 0; i < n; i++){
        if(Prime[arr[i]])
           p[i] = true;
        else
           p[i] = false;
    }
    return p;
}
int main(){
    int n = 6;
    int arr[n] = {1, 2, 3, 4, 5, 6};
    int MAX = -1;
    for(int i = 0; i < n; i++){
        MAX = max(MAX, arr[i]);
    }
    vector<bool> isprime = sieveOfEratosthenes(arr, n, MAX); // boolean array.
    int q = 1;
    while(q--){
        int L = 0, R = 3;
        int cnt = 0; // count
        for(int i = L; i <= R; i++){
            if(isprime[i])
               cnt++;
       }
       cout << cnt << "\n";
   }
   return 0;
}

Output

2

Penjelasan kod di atas

#🎜🎜 kita lebih baik daripada kaedah brute ini digunakan sebelum Kaedah ini jauh lebih pantas kerana kerumitan masa sekarang ialah

O(Q*N)

iaitu jauh lebih baik daripada kerumitan sebelumnya.

Dalam pendekatan ini, kami mengira unsur-unsur dan menandakannya sebagai perdana atau bukan perdana, oleh itu, ini mengurangkan kerumitan kami. Di samping itu, kami juga menggunakan Ayak Eratosthenes, yang akan membantu kami mencari nombor perdana dengan lebih cepat. Dalam kaedah ini, kami melabelkan semua nombor sebagai perdana atau bukan perdana dengan O(N*log(log(N)))

kerumitan dengan melabelkan nombor dengan faktor perdana.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah mencari bilangan nombor perdana dalam subarray dalam O(Q*N) menggunakan Ayak Eratosthenes. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan cara lengkap untuk menyelesaikan masalah ini (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain, seperti C, java, python dan bahasa lain.

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