Рубрики

Наибольшее число не больше N, которое может стать простым после перестановки его цифр

Для заданного числа N задача состоит в том, чтобы найти наибольшее число, меньшее или равное данному числу N, чтобы при перестановке его цифр оно могло стать простым.

Примеры:

Input : N = 99 
Output : 98
Explanation : We can rearrange the digits of 
98 to 89 and 89 is a prime number. 

Input : N = 84896
Output : 84896
Explanation : We can rearrange the digits of 
84896 to 46889 which is a prime number.

Ниже приведен алгоритм для нахождения такого наибольшего числа num <= N , чтобы цифры num можно было переставить, чтобы получить простое число:

Шаг предварительной обработки : Создайте список всех простых чисел, меньших или равных данному числу N. Это можно сделать эффективно, используя сито Эратосфена .

Основные шаги : Основная идея состоит в проверке всех чисел от N до 1, если любое из чисел может быть перетасовано для образования простого числа. Первый найденный номер будет ответом.

Для этого выполните цикл от N до 1 и для каждого числа:

  1. Извлеките цифры данного числа и сохраните их в векторе.
  2. Сортируйте этот вектор, чтобы получить наименьшее число, которое можно сформировать с помощью этих цифр.
  3. Для каждой перестановки этого вектора мы должны сформировать число и проверить, является ли сформированное число простым или нет. Здесь мы используем шаг предварительной обработки.
  4. Если оно простое, то мы останавливаем цикл, и это наш ответ.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ Программа для поиска числа меньше
// или равно N так, что перестановка
// цифры получают простое число

  
#include <bits/stdc++.h>

using namespace std;

  
// Предварительно обработанный вектор для хранения простых чисел

vector<bool> prime(1000001, true);

  
// Функция для генерации простых чисел с использованием
// сито из эратостенеза

void sieve()

{

    // Применение сита Эратосфена

    prime[0] = prime[1] = false;

  

    for (long long i = 2; i * i <= 1000000; i++) {

  

        if (prime[i]) {

            for (long long j = i * i; j <= 1000000; j += i)

                prime[j] = false;

        }

    }

}

  
// Функция, чтобы найти число меньше, чем
// или равно N так, что перестановка
// цифры получают простое число

int findNumber(int n)

{

    vector<int> v;

    bool flag = false;

  

    int num;

  

    // Выполнить цикл от n до 1

    for (num = n; num >= 1; num--) {

  

        int x = num;

  

        // Очистка вектора

        v.clear();

  

        // Извлечение цифр

        while (x != 0) {

            v.push_back(x % 10);

  

            x /= 10;

        }

  

        // Сортировка вектора по наименьшему

        // номер с использованием цифр

        sort(v.begin(), v.end());

  

        // Проверяем всю перестановку текущего числа

        // для простоты

        while (1) {

            long long w = 0;

  

            // Пройдите вектор для числа

            for (auto u : v)

                w = w * 10 + u;

  

            // Если простое число существует

            if (prime[w]) {

  

                flag = true;

                break;

            }

  

            if (flag)

                break;

  

            // генерируем следующую перестановку вектора

            if (!next_permutation(v.begin(), v.end()))

                break;

        }

  

        if (flag)

            break;

    }

  

    // Обязательный номер

    return num;

}

  
// Код драйвера

int main()

{

    sieve();

  

    int n = 99;

    cout << findNumber(n) << endl;

  

    n = 84896;

    cout << findNumber(n) << endl;

  

    return 0;

}

python3

# Программа Python 3, чтобы найти число меньше
# или равно N так, что перестановка
# цифры получают простое число

from math import sqrt

  

def next_permutation(a):

      

    # Создать лексикографически

    # следующая перестановка на месте.

  

    # https://en.wikipedia.org/wiki/Permutation

    # Generation_in_lexicographic_order

    # Вернуть false, если следующей перестановки нет.

  

    # Найти самый большой индекс я такой, что

    # a [i] <a [i + 1]. Если такого индекса нет,

    # перестановка является последней перестановкой

    for i in reversed(range(len(a) - 1)):

        if a[i] < a[i + 1]:

            break # нашел

    else: # без перерыва: не найдено

        return False # нет следующей перестановки

  

    # Найти самый большой индекс j больше, чем я

    # такое, что a [i] <a [j]

    j = next(j for j in reversed(range(i + 1, len(a))) 

                                      if a[i] < a[j])

  

    # Поменяйте местами значение a [i] со значением a [j]

    a[i], a[j] = a[j], a[i]

  

    # Обратная последовательность от [i + 1] до и

    # включая последний элемент a [n]

    a[i + 1:] = reversed(a[i + 1:])

    return True

  
# Предварительно обработанный вектор для хранения простых чисел

prime = [True for i in range(1000001)]

  
# Функция для генерации простых чисел с использованием
# сито из эратостенеза

def sieve():

      

    # Применение сита Эратосфена

    prime[0] = False

    prime[1] = False

  

    for i in range(2,int(sqrt(1000000)) + 1, 1):

        if (prime[i]):

            for j in range(i * i, 1000001, i):

                prime[j] = False

  
# Функция, чтобы найти число меньше, чем
# или равно N так, что перестановка
# цифры получают простое число

def findNumber(n):

    v = []

    flag = False

      

    # Выполнить цикл от n до 1

    num = n

    while(num >= 1):

        x = num

          

        v.clear()

  

        # Извлечение цифр

        while (x != 0):

            v.append(x % 10)

  

            x = int(x / 10)

  

        # Сортировка вектора по наименьшему

        # номер с использованием цифр

        v.sort(reverse = False)

  

        # Проверьте все перестановки текущего номера

        # для первичности

        while (1):

            w = 0

  

            # Вектор перемещения для числа

            for u in v:

                w = w * 10 + u

  

            # Если простое число существует

            if (prime[w]):

                flag = True

                break

  

            if (flag):

                break

  

            # генерация следующей перестановки вектора

            if (next_permutation(v) == False):

                break

  

        if (flag):

            break

          

        num -= 1

  

    # Обязательный номер

    return num

  
Код водителя

if __name__ == '__main__':

    sieve()

  

    n = 99

    print(findNumber(n))

  

    n = 84896

    print(findNumber(n))

  
# Этот код предоставлен
# Surendra_Gangwar

Выход:

98
84896

Рекомендуемые посты:

Наибольшее число не больше N, которое может стать простым после перестановки его цифр

0.00 (0%) 0 votes