Trong bài viết này, chúng tôi sẽ giải thích mọi thứ về cách tìm số cặp số nguyên tố trong một mảng bằng C ++. Chúng ta có một mảng arr [] các số nguyên và chúng ta cần tìm tất cả các cặp số nguyên tố có thể có trong nó. Vì vậy, đây là ví dụ cho vấn đề -
Input : arr[ ] = { 1, 2, 3, 5, 7, 9 }
Output : 6
From the given array, prime pairs are
(2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (5, 7)
Input : arr[] = {1, 4, 5, 9, 11}
Output : 1 Phương pháp tiếp cận để tìm giải pháp
Phương pháp tiếp cận vũ phu
Bây giờ chúng ta sẽ thảo luận về cách tiếp cận cơ bản nhất, tức là cách tiếp cận Brute Force và cố gắng tìm một cách tiếp cận khác vì cách tiếp cận này không hiệu quả lắm.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
bool p[MAX+1];
memset(p, true, sizeof(p));
p[1] = false;
p[0] = false;
for(int i = 2; i * i <= MAX; i++){
if(p[i] == true){
for(int j = i*2; j <= MAX; j += i){
p[j] = false;
}
}
}
for(int i = 0; i < n; i++){
if(p[arr[i]] == true)
prime[i] = true;
}
}
int main(){
int arr[] = {1, 2, 3, 5, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]); // size of our array.
int answer = 0; // counter variable to count the number of prime pairs.
int MAX = INT_MIN; // Max element
for(int i = 0; i < n; i++){
MAX = max(MAX, arr[i]);
}
bool prime[n]; // boolean array that tells if the element is prime or not.
memset(prime, false, sizeof(prime)); // initializing all the elements with value of false.
seiveOfEratosthenes(arr, prime, n, MAX);
for(int i = 0; i < n-1; i++){
for(int j = i+1; j < n; j++){
if(prime[i] == true && prime[j] == true)
answer++;
}
}
cout << answer << "\n";
return 0;
} Đầu ra
6
Trong cách tiếp cận này, chúng tôi đang tạo một mảng bool sẽ cho chúng tôi biết liệu bất kỳ phần tử nào là số nguyên tố hay không, và sau đó chúng tôi sẽ xem xét tất cả các cặp có thể có và kiểm tra xem cả hai số trong cặp đó có phải là số nguyên tố hay không. Nếu là số nguyên tố, hãy tăng câu trả lời lên một và tiếp tục.
Nhưng cách tiếp cận này không hiệu quả lắm vì độ phức tạp về thời gian của nó là O (N * N) , trong đó N là kích thước mảng của chúng ta, vì vậy, bây giờ chúng ta sẽ làm cho cách tiếp cận này nhanh hơn.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, hầu hết các mã sẽ giống nhau, nhưng thay đổi quan trọng là thay vì xem xét tất cả các cặp có thể có, chúng tôi sẽ tính toán chúng bằng công thức.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
bool p[MAX+1];
memset(p, true, sizeof(p));
p[1] = false;
p[0] = false;
for(int i = 2; i * i <= MAX; i++){
if(p[i] == true){
for(int j = i*2; j <= MAX; j += i){
p[j] = false;
}
}
}
for(int i = 0; i < n; i++){
if(p[arr[i]] == true)
prime[i] = true;
}
}
int main(){
int arr[] = {1, 2, 3, 5, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]); // size of our array.
int answer = 0; // counter variable to count the number of prime pairs.
int MAX = INT_MIN; // Max element
for(int i = 0; i < n; i++){
MAX = max(MAX, arr[i]);
}
bool prime[n]; // boolean array that tells if the element is prime or not.
memset(prime, false, sizeof(prime)); // initializing all the elements with value of false.
seiveOfEratosthenes(arr, prime, n, MAX);
for(int i = 0; i < n; i++){
if(prime[i] == true)
answer++;
}
answer = (answer * (answer - 1)) / 2;
cout << answer << "\n";
return 0;
} Đầu ra
6
Như bạn có thể thấy, hầu hết mã đều giống với cách tiếp cận trước đó, nhưng thay đổi quan trọng làm giảm đáng kể độ phức tạp của chúng tôi là công thức mà chúng tôi đã sử dụng, tức là n (n-1) / 2, sẽ tính toán số các cặp số nguyên tố.
Giải thích về Quy tắc trên
Trong đoạn mã này, chúng ta đang sử dụng Sieve of Eratosthenes để đánh dấu tất cả các số nguyên tố cho đến phần tử Max mà chúng ta có trong mảng. Trong một mảng bool khác, chúng tôi đánh dấu các phần tử một cách khôn ngoan nếu chúng là số nguyên tố hay không.
Cuối cùng, chúng ta đang duyệt qua toàn bộ mảng, tìm tổng số các số nguyên tố có mặt và tìm tất cả các cặp có thể có bằng cách sử dụng công thức n * (n-1) / 2. Với công thức này, độ phức tạp của chúng ta được giảm xuống O (N) , trong đó N là kích thước mảng của chúng ta.
Kết luận
Trong bài này, chúng ta giải bài toán tìm Số cặp nguyên tố có trong một mảng theo độ phức tạp thời gian O (n). Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác.