0

Условие задачи:

Найти наименьшее и наибольшее натуральные числа, произведение цифр в которых равно заданному натуральному числу M или сообщить, что таких чисел не существует. Для записи искомых чисел нельзя использовать цифры 0 и 1.

Входные данные В единственной строке входного файла INPUT.TXT записано натуральное число M (2 ≤ M ≤ 1000).

Выходные данные В единственную строку выходного файла OUTPUT.TXT нужно вывести два натуральных числа в неубывающем порядке. Если таких чисел не существует, то вывести -1 -1.

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

bool check_prime(int n)
{
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}

int main()
{
    int n;
    cin >> n;
    for (size_t i = 11; i * i <= n; i += 2)
    {
        if (check_prime(i) && n % i == 0) //если существует простой делитель больше 9, то число непредставимо
        {
            cout << -1 << " " << -1;
            return 0;
        }
    }
    vector<int> a,b; //a - максимальное, b - минимальное 
    int m = n;
    for (size_t i = 2; i < 10 && n != 1; i++)
    {
        while (n % i == 0)
        {
            a.push_back(i);
            n /= i;
        }
    }
    for (size_t i = 9; i > 1 && m != 1; i--)
    {
        while (m % i == 0)
        {
            b.push_back(i);
            m /= i;
        }
    }
    for (auto i = b.rbegin(); i != b.rend(); i++)
    {
        cout << *i;
    }
    cout << " ";
    for (auto i = a.rbegin(); i != a.rend(); i++)
    {
        cout << *i;
    }
}

На одном из тестов неверный ответ. В чем может быть проблема?

1 ответ 1

4

Давайте возьмем число... ну... 57 = 3*19, вот.

Пошла ваша проверка...

for (size_t i = 11; i * i <= n; i += 2)

Стоп-стоп! 11*11==121, явно больше 57 - значит, мы проскакиваем эту проверку вообще!

Досадно, но идем дальше, потому что еще не все потеряно...

for (size_t i = 2; i < 10 && n != 1; i++)
{
    while (n % i == 0)
    {
        a.push_back(i);
        n /= i;
    }
}

Вот здесь бы проверить, а не осталось ли n большим 1 (реально - большим 10), но раз мы этого не делаем - вот теперь уже да, таки все потеряно. Программа выведет 3 3, что, как вы понимаете, как ни множь - никак не даст 57...

Я бы вашу проверку с 11 (понимаете, в чем ее ошибка?...) убрал вообще и проверял бы число уже после разложения на простые однозначные.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.