นับจำนวนในช่วงที่มีความแตกต่างระหว่างผลรวมของหลักที่ตำแหน่งคู่และคี่เป็น Prime ใน C++

กำหนดตัวเลขสองตัวเริ่มต้นและสิ้นสุดเป็นตัวแปรช่วง เป้าหมายคือการหาจำนวนตัวเลขที่อยู่ในช่วงนี้ [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[size][90][90][2] นี่คือขนาดกำลังของ 10 ดังนั้นจำนวนที่มากที่สุดที่อินพุตจะเป็น 10 ^ขนาด .

ในแต่ละการเรียกซ้ำเพื่อตรวจสอบฟังก์ชัน (int place, int eve, int od, int temp, vector vec) เราจะสร้างตัวเลขโดยวางตัวเลข 0 ถึง 9 จากซ้ายไปขวา

ใน arr[size][x][y][temp], x คือผลรวมของหลักในตำแหน่งคู่ที่วางไม่เกิน x และ y สำหรับผลรวมของหลักคี่ที่วางไม่เกิน y ตรวจสอบว่าความแตกต่างที่ต้องการคือจำนวนเฉพาะหรือไม่ใช้อาร์เรย์ arr_2[] ซึ่งเก็บจำนวนเฉพาะทั้งหมดไม่เกิน 100 ตามลำดับ

• รับตัวแปรเริ่มต้นและสิ้นสุดเป็นอินพุต
• ใช้อาร์เรย์โกลบอล arr[size][90][90][2] และอาร์เรย์ arr_2[] สำหรับจำนวนเฉพาะสูงสุด 100
• การตรวจสอบฟังก์ชัน (int place, int eve, int od, int temp, vector vec) รับตำแหน่งปัจจุบันของหลักเป็นสถานที่, ผลรวมปัจจุบันของตำแหน่ง eve ตำแหน่งเป็นคู่และตำแหน่งคี่เป็น od, ค่าของ temp และเวกเตอร์ vec ที่มีตัวเลข
• มันเติมค่าที่ arr[place][eve][od][temp] แบบเรียกซ้ำ
• นำค่าเริ่มต้นสำหรับองค์ประกอบปัจจุบันเป็น count=0
• สำหรับตำแหน่งปัจจุบัน ตรวจสอบว่าสถานที่นั้นเป็นตำแหน่งสุดท้ายโดยใช้ if(place ==vec.size()) ถ้าใช่ ให้ตรวจสอบว่าตำแหน่งนั้นเป็นคี่หรือคู่
• if(vec.size() &1) ให้ผลลัพธ์เป็นจริง ตำแหน่งปัจจุบันจะเป็นคี่ ดังนั้นให้สลับอีฟกับ od เนื่องจากเป็นตัวเลขความยาวคี่
• คำนวณ temp_2 เป็นผลต่างของผลรวมในวันก่อนหน้า
• ใช้ for loop ข้าม arr_2[] และตรวจสอบว่าพบ temp_2 หรือไม่ ถ้าใช่ แสดงว่าเป็นไพรม์ ดังนั้นให้คืนค่า 1 อย่างอื่นคืนค่า 0
• ถ้า arr[place][eve][od][temp] ได้รับการคำนวณแล้ว มันจะไม่เป็น -1 ดังนั้นให้ส่งคืน
• ถ้า temp ไม่ใช่ศูนย์ ให้ตั้งค่า temp_3=9 Temp_3 คือขีดจำกัดสูงสุดของตัวเลขที่เราวางได้ หากเป็น 0 ให้วาง vec[place] มิฉะนั้น ตัวเลขจะน้อยกว่าอยู่แล้ว ดังนั้นให้วางหลักใดๆ ว่า 9
• ข้ามหลักจาก 0 ถึง temp_3. หากตำแหน่งปัจจุบันเป็นเลขคี่ ให้อัปเดต set_odd =set_odd + i; (ผลรวมตำแหน่งคี่ก่อนหน้า + ตัวเลขปัจจุบัน i )
• หากตำแหน่งปัจจุบันเป็นคู่ ให้อัปเดต set_even =set_even + i; (ผลรวมตำแหน่งคู่ก่อนหน้า + ตัวเลขปัจจุบัน i )
• ตั้งค่าการนับ +=ตรวจสอบ (สถานที่ + 1, set_even, set_odd, set_temp, vec); และส่งคืน arr[place][eve][od][temp] =count.
• Function place_prime(int val) ใช้ค่าตัวเลขและสร้างเวกเตอร์ vec ที่มีตัวเลขจาก LSB ถึง MSB
• ตั้งค่าอาร์เรย์ทั้งหมด arr[][][][] ด้วย -1.
• Take count =ตรวจสอบ (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