Chúng tôi được cung cấp một số dương n làm đầu vào. Mục đích là tìm số lượng các cặp có thể có (i, j) sao cho mỗi cặp có tổng (i + j) là số nguyên tố và nhỏ hơn n. Ngoài ra i! =J và i, j> =1 Nếu n là 4 thì chỉ có thể có 1 cặp là (1,2). Ở đây 1 + 2 =3 là số nguyên tố và nhỏ hơn 4. Ngoài ra 1,2> =1.
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - n =7
Đầu ra - Đếm các cặp có tổng là số nguyên tố và nhỏ hơn n là - 3
Giải thích - Các cặp sẽ là (1,2), (1,4), (2,3). Tổng 3, 5, 5 là số nguyên tố và nhỏ hơn 7.
Đầu vào - n =10
Đầu ra - Đếm các cặp có tổng là số nguyên tố và nhỏ hơn n là - 6
Giải thích -
Các cặp sẽ là (1,2), (1,4), (2,3), (1,6), (2,5), (3,4).
Tổng 3, 5, 5, 7, 7, 7 là số nguyên tố và nhỏ hơn 10.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, trước tiên chúng ta sẽ tìm tất cả các số nguyên tố nhỏ hơn n bằng cách sử dụng Sieve of Sundaram trong function check_prime (bool check [], int temp).
Ngoài ra đối với mỗi tạm thời số lẻ, số lượng các cặp riêng biệt có nhiệt độ tổng sẽ là tạm thời / 2.
Ngoại trừ 2 số nguyên tố đều là số lẻ nên nếu chúng ta tìm thấy bất kỳ số nguyên tố nào nhỏ hơn n thì chúng ta sẽ thêm temp / 2 để đếm các cặp.
-
Lấy biến n làm đầu vào.
-
Hàm prime_pair (int n) nhận n và trả về số lượng các cặp có tổng là số nguyên tố và nhỏ hơn n.
-
Lấy số lượng ban đầu là 0.
-
Như Sieve of Sundaram tạo ra các số nguyên tố nhỏ hơn 2 * n + 2 cho đầu vào n. Chúng tôi giảm n xuống một nửa và lưu trữ ở nhiệt độ thứ 2.
-
Tạo mảng Kiểm tra [] độ dài temp_2 để đánh dấu tất cả các số có dạng (i + j + 2 * i * j) là Đúng. Khởi tạo nó với tất cả các phần tử là false.
-
Sử dụng hàm check_prime (bool check [], int temp), khởi tạo check [] với true cho các số có dạng (i + j + 2 * i * j). Và số tiền này
-
Bây giờ, hãy kiểm tra qua Kiểm tra [] bằng cách sử dụng vòng lặp for từ chỉ mục i =0 đến i
-
Đối với mỗi lần kiểm tra [i] là sai, số nguyên tố sẽ là temp =2 * i + 1.
-
Các cặp cộng lại với nhiệt độ sẽ là tạm thời / 2.
-
Thêm nhiệt độ / 2 để đếm.
-
Ở cuối vòng lặp for, chúng ta sẽ có tổng các cặp có tổng là số nguyên tố và nhỏ hơn n.
-
Kết quả là số lượt trả lại.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
void check_prime(bool check[], int temp){
for (int i=1; i<=temp; i++){
for (int j=i; (i + j + 2*i*j) <= temp; j++){
check[i + j + 2*i*j] = true;
}
}
}
int prime_pair(int n){
int count = 0;
int temp;
int temp_2 = (n-2)/2;
bool check[temp_2 + 1];
memset(check, false, sizeof(check));
check_prime(check, temp_2);
for (int i=1; i <= temp_2; i++){
if (check[i] == false){
temp = 2*i + 1;
count += (temp / 2);
}
}
return count;
}
int main(){
int n = 10;
cout<<"Count of pairs with sum as a prime number and less than n are: " <<prime_pair(n);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of pairs with sum as a prime number and less than n are: 6