Cho hai số bắt đầu và kết thúc dưới dạng các biến phạm vi. Mục đích là để tìm số lượng các số nằm trong phạm vi này [bắt đầu, kết thúc] và có sự khác biệt của tổng các chữ số ở vị trí chẵn và tổng các chữ số ở các vị trí lẻ là Nguyên tố.
Đó là (tổng các chữ số ở vị trí chẵn) - (tổng các chữ số ở vị trí lẻ) =một số nguyên tố
Hãy cho chúng tôi hiểu với các ví dụ.
Ví dụ
Đầu vào - start =230, end =270
Đầu ra - Đếm Số trong Dải có hiệu số giữa Tổng các chữ số ở vị trí chẵn và lẻ là Nguyên tố là:6
Giải thích - (Các) số từ 230 đến 270 đáp ứng điều kiện là:
240 (4-2 là 2), 250 (5-2 là 3), 251 (5-3 là 2), 261 (6-3 là 3), 262 (6-4 là 2), 270 (7-2 là 5).
Tất cả những khác biệt này là 2, 3 và 5 là số nguyên tố.
Đầu vào - start =1101, end =1120
Đầu ra - Đếm Số trong Dải có hiệu số giữa Tổng các chữ số ở vị trí chẵn và lẻ là Nguyên tố là:1
Giải thích - (Các) số từ 1101 đến 1120 đáp ứng điều kiện là:
1120 (3-1 là 2). 2 là số nguyên tố.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong phương pháp này, chúng tôi sử dụng phương pháp lập trình động và lưu trữ số đếm các số có hiệu số Nguyên tố của tổng các chữ số vị trí chẵn và lẻ. Mảng này sẽ là arr [size] [90] [90] [2]. Ở đây kích thước là lũy thừa của 10. Vì vậy, số lớn nhất khi đầu vào sẽ là 10 size .
Trong mỗi lệnh gọi đệ quy để kiểm tra hàm (int place, int eve, int od, int temp, vector
Trong arr [size] [x] [y] [temp], x là tổng các chữ số ở vị trí chẵn được đặt cho đến x và y là tổng các chữ số lẻ được đặt đến y. Kiểm tra xem sự khác biệt bắt buộc có phải là Số nguyên tố hay không bằng cách sử dụng mảng arr_2 [] để lưu trữ tất cả các số nguyên tố lên đến 100 theo thứ tự.
- Lấy các biến bắt đầu và kết thúc làm đầu vào.
- Lấy mảng toàn cục arr [size] [90] [90] [2] và mảng arr_2 [] cho các số nguyên tố lên đến 100.
- Kiểm tra hàm (int place, int eve, int od, int temp, vector
vec) lấy vị trí hiện tại của chữ số làm vị trí, tổng hiện tại của các chữ số vị trí đêm trước là chữ số vị trí chẵn và lẻ là od, giá trị của tạm thời và vec-tơ vec-tơ có các chữ số. - Nó điền các giá trị tại arr [place] [eve] [od] [temp] một cách đệ quy.
- Lấy giá trị ban đầu cho phần tử hiện tại là count =0.
- Đối với vị trí hiện tại, hãy kiểm tra xem vị trí có phải là vị trí cuối cùng hay không bằng cách sử dụng if (place ==vec.size ()). Nếu có, hãy kiểm tra xem vị trí đó là lẻ hay chẵn.
- if (vec.size () &1) cho kết quả đúng thì vị trí hiện tại là số lẻ, vì vậy hãy hoán đổi eve với od vì nó là số có độ dài lẻ.
- Tính toán temp_2 dưới dạng chênh lệch của các tổng tính đến thời điểm khác nhau.
- Sử dụng vòng lặp for, traverse arr_2 [] và kiểm tra xem có tìm thấy temp_2 hay không. Nếu có thì số nguyên tố của nó. Vì vậy, trả về 1 khác trả về 0.
- Nếu arr [place] [eve] [od] [temp] đã được tính toán rồi thì nó sẽ không phải là -1 vì vậy hãy trả lại nó.
- Nếu tạm thời khác 0 thì hãy đặt temp_3 =9. Temp_3 là giới hạn tối đa của chữ số mà chúng tôi có thể đặt. Nếu nó là 0 thì hãy đặt vec [place] nếu không thì số đã nhỏ hơn nên đặt bất kỳ chữ số nào là 9.
- Chuyển các chữ số từ 0 đến temp_3. Nếu vị trí hiện tại là lẻ thì cập nhật set_odd =set_odd + i; (tổng vị trí lẻ trước đó + chữ số i hiện tại).
- Nếu vị trí hiện tại là chẵn thì hãy cập nhật set_even =set_even + i; (tổng vị trí chẵn trước đó + chữ số i hiện tại).
- Đặt count + =check (place + 1, set_even, set_odd, set_temp, vec); và trả về arr [place] [eve] [od] [temp] =count.
- Hàm place_prime (int val) nhận số val và tạo một vec-tơ chứa chữ số của nó từ LSB đến MSB.
- Đặt toàn bộ mảng arr [] [] [] [] bằng -1.
- Hãy đếm =kiểm tra (0, 0, 0, 0, vec) sẽ trả về kết quả ở cuối.
- Trả về kết quả là số lượng.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
const int size = 18;
int arr[size][90][90][2];
//firt 100 prime Numbers
int arr_2[] = {
2,
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97
};
int check(int place, int eve, int od, int temp, vector < int > vec) {
int count;
int temp_3;
if (place == vec.size()) {
if (vec.size() & 1) {
swap(od, eve);
}
int temp_2 = eve - od;
for (int i = 0; i < 24; i++) {
if (temp_2 == arr_2[i]) {
return 1;
}
}
return 0;
}
if (arr[place][eve][od][temp] != -1) {
int set = arr[place][eve][od][temp];
return set;
}
if (temp) {
temp_3 = 9;
} else {
temp_3 = vec[place];
}
for (int i = 0; i <= temp_3; i++) {
int set_temp = temp;
int set_even = eve;
int set_odd = od;
if (i < vec[place]) {
set_temp = 1;
}
if (place & 1) {
set_odd = set_odd + i;
} else {
set_even = set_even + i;
}
count += check(place + 1, set_even, set_odd, set_temp, vec);
}
return arr[place][eve][od][temp] = count;
}
int place_prime(int val) {
vector < int > vec;
while (val) {
vec.push_back(val % 10);
val = val / 10;
}
reverse(vec.begin(), vec.end());
memset(arr, -1, sizeof(arr));
int count = check(0, 0, 0, 0, vec);
return count;
}
int main() {
int start = 20, end = 80;
int count = place_prime(end) - place_prime(start - 1);
cout << "Count of Numbers in Range with difference between Sum of digits at even and odd positions as Prime are: " << count;
return 0;
} Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Đầu ra
Count of Numbers in Range with difference between Sum of digits at even and odd positions as Prime are: 15