ตัวเลข Emirp ใน C++

Emirp number คือจำนวนเฉพาะชนิดพิเศษที่เป็นจำนวนเฉพาะซึ่งหลักเมื่อกลับด้านจะสร้างจำนวนเฉพาะอีกจำนวนหนึ่ง (จำนวนเฉพาะนี้แตกต่างจากจำนวนเดิม)

Emirp คือส่วนกลับของจำนวนเฉพาะ

จำนวนเฉพาะบางจำนวนที่ไม่ใช่ Emirp คือ palindromic prime และจำนวนเฉพาะหลักเดียว

ตัวเลข Emirp บางส่วน คือ 13, 17, 37, 733

โปรแกรมพิมพ์ตัวเลข emirp ทั้งหมดที่น้อยกว่า n.

ที่นี่ เราได้รับตัวเลข n และเราต้องพิมพ์ หมายเลข emirp . ทั้งหมด น้อยกว่าหรือเท่ากับ n.

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล: n =40

ผลลัพธ์: 13, 17, 31, 37

แนวทางการแก้ปัญหา

ในการหาจำนวนรวมทั้งหมดน้อยกว่าจำนวนที่กำหนด เราจำเป็นต้องค้นหาจำนวนเฉพาะทั้งหมดที่น้อยกว่า n แล้วตรวจสอบว่าจำนวนที่เกิดขึ้นจากการกลับหลักเป็นจำนวนเฉพาะมากกว่าจำนวน Emirp หรือไม่ พิมพ์ออกมา

สำหรับการหาจำนวนเฉพาะจนถึง n แล้วตรวจสอบตัวเลขย้อนกลับ วิธีที่ดีที่สุดคือการใช้ตะแกรงของ Eratosthenes

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int reverseDigits(int x) {

   int digitRev = 0;
   while (x > 0)
   {
      digitRev = (digitRev*10) + x%10;
      x = x/10;
   }
   return digitRev;
}

void findAllEmirpNumber(int n) {

   bool primeNo[10001];
   memset(primeNo, true, sizeof(primeNo));

   for (int p=2; p*p<=10001; p++)
   {
      if (primeNo[p] == true)
      {
         for (int i=p*2; i<=10001; i += p)
            primeNo[i] = false;
      }
   }
   for (int p=2; p<=n; p++)
   {
      if (primeNo[p])
      {
         int revNo = reverseDigits(p);
         if (p != revNo && primeNo[revNo]) {
         cout<<p<<"\t";
         if(revNo <= n)
          cout<<revNo<<"\t";
         primeNo[revNo] = false;
         }
      }
   }
}

int main()
{
   int n = 40;
   cout<<"All Emirp numbers less than or equal to "<<n<<" are\n";
   findAllEmirpNumber(n);
   return 0;
}

ผลลัพธ์

All Emirp numbers less than or equal to 40 are 13 31 17 37