Tìm số nguyên tố đặc biệt lớn nhất nhỏ hơn hoặc bằng một số nhất định trong C ++

Giả sử chúng ta có một số n. Chúng ta phải tìm số nguyên tố đặc biệt lớn nhất nhỏ hơn hoặc bằng N. Số nguyên tố đặc biệt là một số, có thể được tạo ra bằng cách đặt các chữ số lần lượt, vì vậy tất cả các số kết quả đều là số nguyên tố.

Ở đây chúng ta sẽ sử dụng Sieve Of Eratosthenes. Chúng ta sẽ tạo mảng sàng lên đến số n. Sau đó, bắt đầu lặp lại từ số N, bằng cách kiểm tra xem số đó có phải là số nguyên tố hay không. Khi đây là số nguyên tố, hãy kiểm tra xem đây có phải là số nguyên tố đặc biệt hay không.

Ví dụ

#include<iostream>
using namespace std;
bool isSpecialPrime(bool sieve[], int num) {
   while (num) {
      if (!sieve[num]) {
         return false;
      }
      num /= 10;
   }
   return true;
}
void findSpecialPrime(int N) {
   bool sieve[N + 10];
   for(int i = 0; i<N+10; i++){
      sieve[i] = true;
   }
   sieve[0] = sieve[1] = false;
   for (long long i = 2; i <= N; i++) {
      if (sieve[i]) {
         for (long long j = i * i; j <= N; j += i) {
            sieve[j] = false;
         }
      }
   }
   while (true) {
      if (isSpecialPrime(sieve, N)) {
         cout << N << '\n';
         break;
      }
      else
         N--;
   }
}
int main() {
   cout << "Special prime in range (2 -> 400): ";
   findSpecialPrime(400);
   cout << "Special prime in range (2 -> 100): ";
   findSpecialPrime(100);
}

Đầu ra

Special prime in range (2 -> 400): 379
Special prime in range (2 -> 100): 79