C++에서 주어진 숫자보다 작거나 같은 가장 큰 특수 소수 찾기

숫자 n이 있다고 가정합니다. N보다 작거나 같은 가장 큰 특수 소수를 찾아야 합니다. 특수 소수는 숫자이며 숫자를 차례로 배치하여 만들 수 있으므로 결과로 나오는 모든 숫자는 소수입니다.

여기서 우리는 에라토스테네스의 체를 사용할 것입니다. 숫자 n까지 체 배열을 생성합니다. 그런 다음 숫자가 소수인지 확인하여 숫자 N에서 다시 시작합니다. 이것이 소수일 때 이것이 특수 소수인지 확인하십시오.

예시

#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);
}

출력

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