Đếm số trong khoảng có hiệu tổng chữ số vị trí chẵn lẻ là số nguyên tố trong C++

Cho hai số start và end làm biến khoảng. Mục tiêu: đếm số trong khoảng [start, end] có hiệu giữa tổng chữ số vị trí chẵn và tổng chữ số vị trí lẻ là số nguyên tố.

Tức: (tổng chữ số vị trí chẵn) - (tổng chữ số vị trí lẻ) = số nguyên tố.

Hiểu qua ví dụ

Đầu vào: start = 230, end = 270

Đầu ra: Số lượng số thỏa mãn: 6

Giải thích: Các số 230-270 thỏa mãn:

240 (4-2=2), 250 (5-2=3), 251 (5-3=2), 261 (6-3=3), 262 (6-4=2), 270 (7-2=5).

Hiệu là 2, 3, 5 - đều là số nguyên tố.

Đầu vào: start = 1101, end = 1120

Đầu ra: Số lượng số thỏa mãn: 1

Giải thích: Số 1120 (3-1=2), 2 là số nguyên tố.

Phương pháp sử dụng

Sử dụng quy hoạch động lưu đếm số có hiệu tổng chẵn/lẻ là số nguyên tố. Mảng arr[size][90][90][2], size là lũy thừa 10. Số lớn nhất đầu vào 10^size.

Mỗi gọi đệ quy check(int place, int eve, int od, int temp, vector<int> vec) xây dựng số bằng cách đặt chữ số 0-9 từ trái sang phải.

Trong arr[size][x][y][temp], x = tổng chữ số vị trí chẵn, y = tổng vị trí lẻ. Kiểm tra hiệu có phải nguyên tố bằng mảng arr_2[] lưu 24 số nguyên tố đầu tiên ≤ 100.

Nhập start, end.
Mảng toàn cục arr[size][90][90][2] và arr_2[] số nguyên tố.
Hàm check() điền mảng đệ quy.
Nếu place == vec.size(): nếu độ dài lẻ (vec.size() & 1) hoán đổi eve, od. Tính temp_2 = eve - od. Duyệt arr_2[] nếu tìm thấy trả về 1 else 0.
Nếu arr[place][eve][od][temp] != -1 trả về giá trị.
temp_3 = 9 nếu temp != 0 else vec[place].
Duyệt i = 0..temp_3: cập nhật set_even hoặc set_odd tùy vị trí chẵn/lẻ, đệ quy.
Hàm place_prime(int val) tạo vector chữ số, khởi tạo mảng -1, gọi check(0,0,0,0,vec).

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 
const int size = 18; 
int arr[size][90][90][2]; 
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) { 
        return arr[place][eve][od][temp]; 
    } 
    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; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of Numbers in Range with difference between Sum of digits at even and odd positions as Prime are: 15