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

Question

Недавно я играл с поиском делителей чисел и решил попробовать создать программу, которая печатает все способы выразить число 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 и заканчиваться на 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;
}

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

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

РЕДАКТИРОВАТЬ: Попробовал с помощью 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, который возвращает структуру, содержащую оба значения.

Answer 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 --- вам действительно не нужно часто очищать поток.Быстрее разрешить выходной буфер так, как он хочет.

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