Получить все способы представить число в виде произведения двух целых чисел

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

#include <iostream>
#include <cmath>

int main()
{
    int n;
    std::cin >> n;

    int root = std::sqrt(n);
    for(int i = 1; i <= root; i++)
    {
        if(n % i != 0)
            continue;

        int j = n / i;  
        std::cout << i << ", " << j << std::endl;
    }

    return 0;
}

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

Например, если я введу 10 в приведенную выше программу, результаты будут (1, 10), (2, 5); Это правильно, но есть и другие способы умножить два числа и получить 10. Он включает в себя отрицательные числа: (-1, -10), (-2, -5) также являются решениями, поскольку при умножении двух отрицательных чисел вы в конечном итоге с положительным.

Если бы я хотел, чтобы программа работала только с положительными значениями N, но также находила и отрицательные кратные, я мог бы просто напечатать отрицательные версии i и j, поскольку вы можете получить положительное число, только перемножив два положительных или два отрицательных вместе.

Это работает, но теперь я хочу, чтобы этот код работал с отрицательными значениями N. Например, ожидаемый результат для N = -10 будет следующим: (-1, 10), (1, -10), (2, -5), (-2, 5);

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

Я заметил, что могу просто вычислить квадратный корень из абсолютного значения N, затем заставить цикл начинаться с -root и заканчиваться на корне, чтобы пройти и отрицательные делители N. Однако я должен был пропустить 0, потому что деление с 0 не определено, и это привело к сбою. Код, который у меня получился, выглядит так:

#include <iostream>
#include <cmath>

int main()
{
    int n;
    std::cin >> n;

    int root_n = std::sqrt(std::abs(n));
    for(int i = -root_n; i <= root_n; i++)
    {
        if(i == 0 || n % i != 0)
            continue;

        int j = n / i;  
        std::cout << i << ", " << j << std::endl;
    }

    return 0;
}

Он работал правильно для всех тестов, которые я придумал, но я не уверен, что это лучший способ написать его. Есть ли что-то, что я могу улучшить?

Заранее спасибо!

EDIT: Попытался использовать std::div, как предложил Caleth (также использовал дополнение ReSharper в VS, чтобы дать мне предложения по рефакторингу):

#include <iostream>
#include <cstdlib>

int main()
{
    int n;
    std::cin >> n;

    const int sqrt_n = std::sqrt(std::abs(n));
    for(auto i = -sqrt_n; i <= sqrt_n; i++)
    {
        if (i == 0)
            continue;

        const auto div_res = std::div(n, i);
        if (div_res.rem)
            continue;

        std::cout << i << ", " << div_res.quot << std::endl;
    }

    return 0;
}

Вместо того, чтобы вычислять остаток, а затем вычислять частное, я могу просто сделать один вызов std::div, который возвращает структуру, содержащую оба значения.


person Tsvetomir Bonev    schedule 19.03.2019    source источник
comment
Вы можете посмотреть на std::div, который возвращает структуру с обоими частное и остаток за один вызов   -  person Caleth    schedule 19.03.2019


Ответы (1)


Основное наблюдение состоит в том, что отрицательные делители и положительные делители числа одинаковы, за исключением знака. Вы могли бы сэкономить половину времени, если бы смотрели только на положительные числа и самостоятельно обрабатывали знаки. Например,

int main()
{
    int n;
    std::cin >> n;

    int root_n = std::sqrt(std::abs(n));

    for(int i = 1; i <= root_n; i++) \\ don't loop over negative numbers now
    {
        if(n % i != 0) \\ not necessary to check for 0 anymore
            continue;

        int j = n / i;  
        std::cout << i << ", " << j << "\n";
        std::cout << -i << ", " << -j << "\n";  \\ corresponding negative
    }

    return 0;
}

Вы могли заметить, что я удалил std::endl --- вам не нужно часто очищать поток. Быстрее разрешить буфер вывода, как он хочет.

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

person davidlowryduda    schedule 19.03.2019
comment
Теперь, когда я думаю об этом, это действительно имеет смысл! Спасибо! - person Tsvetomir Bonev; 19.03.2019