두 개의 숫자가 범위 변수로 시작하고 끝납니다. 목표는 이 범위 [start,end]에 있는 숫자의 개수를 찾는 것이며 짝수의 자릿수 합과 홀수 위치 자릿수의 합 차이를 소수로 하는 것입니다.
즉, (짝수 위치의 자릿수 합)-(홀수 위치 자릿수 합) =소수
예를 들어 이해합시다.
예를 들어
입력 - 시작 =230, 끝 =270
출력 - 짝수 및 홀수 위치의 자릿수 합이 소수인 범위의 숫자 개수는 다음과 같습니다. 6
설명 - 조건을 충족하는 230에서 270 사이의 숫자는 다음과 같습니다.
240 ( 4-2 는 2 ), 250 ( 5-2 는 3 ), 251 ( 5-3 은 2 ), 261 ( 6-3 은 3 ), 262 ( 6-4 는 2 ), 270 ( 7-2 5 )입니다.
이 모든 차이는 2, 3, 5이며 소수입니다.
입력 - 시작 =1101, 끝 =1120
출력 - 짝수와 홀수 위치의 자릿수 합이 소수인 범위의 숫자 개수는 다음과 같습니다. 1
설명 - 조건을 충족하는 1101에서 1120 사이의 숫자는 다음과 같습니다.
1120(3-1은 2) 2는 프라임입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
여기서 우리는 동적 프로그래밍 접근 방식을 사용하고 짝수 및 홀수 위치 자릿수의 합계의 소수 차이가 있는 숫자의 개수를 저장합니다. 이 배열은 arr[크기][90][90][2]입니다. 여기에서 크기는 10의 거듭제곱입니다. 따라서 입력으로 가장 큰 숫자는 10 size 이 됩니다. .
check(int place, int eve, int od, int temp, vector
arr[size][x][y][temp]에서 x는 x까지 짝수 자리의 자릿수의 합이고 y는 y까지의 홀수 자릿수의 합입니다. 필요한 차이가 소수인지 100까지의 모든 소수를 순서대로 저장하는 배열 arr_2[]를 사용하지 않는지 확인합니다.
- 변수를 입력으로 시작하고 종료합니다.
- 최대 100개의 소수에 대해 전역 배열 arr[size][90][90][2] 및 배열 arr_2[]를 사용합니다.
- 함수 검사(int place, int eve, int od, int temp, vector
vec)는 현재 자릿수를 자릿수로, 이브 위치 자릿수의 현재 합을 짝수로, 홀수 위치 자릿수를 od로, temp 값을 취합니다. 및 숫자가 있는 벡터 vec. - 재귀적으로 arr[place][eve][od][temp]의 값을 채웁니다.
- 현재 요소의 초기값을 count=0으로 취합니다.
- 현재 위치의 경우 if(place ==vec.size())를 사용하여 place가 마지막 위치인지 확인합니다. 그렇다면 해당 위치가 홀수인지 짝수인지 확인하십시오.
- if(vec.size() &1) 결과가 true이면 현재 위치가 홀수이므로 eve를 od로 바꾸면 홀수 길이가 됩니다.
- temp_2를 eve-od로 합계의 차이로 계산합니다.
- for 루프를 사용하여 arr_2[]를 탐색하고 temp_2가 있는지 확인합니다. 그렇다면 그 전성기. 따라서 1을 반환하고 그렇지 않으면 0을 반환합니다.
- arr[place][eve][od][temp]가 이미 계산된 경우 -1이 아니므로 반환합니다.
- temp가 0이 아니면 temp_3=9로 설정합니다. Temp_3은 배치할 수 있는 숫자의 최대 한계입니다. 0이면 vec[place]를 배치하고 그렇지 않으면 숫자가 이미 더 작으므로 아무 숫자나 배치합니다(예:9).
- 0에서 temp_3까지 숫자를 트래버스합니다. 현재 위치가 홀수이면 set_odd =set_odd + i를 업데이트합니다. ( 이전 홀수 위치 합계 + 현재 숫자 i ).
- 현재 위치가 짝수이면 set_even =set_even + i를 업데이트합니다. ( 이전 짝수 위치 합계 + 현재 숫자 i ).
- 세트 개수 +=check(place + 1, set_even, set_odd, set_temp, vec); 반환 arr[place][eve][od][temp] =count.
- place_prime(int val) 함수는 숫자 val을 사용하여 LSB에서 MSB까지의 숫자를 포함하는 벡터 vec를 생성합니다.
- 전체 배열을 -1로 설정합니다.
- 끝에 결과를 반환할 count =check(0, 0, 0, 0, vec)를 취합니다.
- 결과로 개수를 반환합니다.
예시
#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;
} 위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
출력
Count of Numbers in Range with difference between Sum of digits at even and odd positions as Prime are: 15