Факторизация числа?

Question

[avion]

Здравствуйте, имеется код:

#include <iostream>
#include <cstdlib>

using namespace std;

int main() {
    int n = 100005, s = 1;

    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            if (i * j == n) {
                cout << "(" << s << ")" << endl;
                cout << "i = " << i << endl;
                cout << "j = " << j << endl;
                cout << endl;
                s++;
            }
        }
    }
}

Вывод:

(1)
i = 3
j = 33335

(2)
i = 5
j = 20001

(3)
i = 15
j = 6667

(4)
i = 59
j = 1695

(5)
i = 113
j = 885

(6)
i = 177
j = 565

(7)
i = 295
j = 339

(8)
i = 339
j = 295

(9)
i = 565
j = 177

(10)
i = 885
j = 113

(11)
i = 1695
j = 59

(12)
i = 6667
j = 15

(13)
i = 20001
j = 5

(14)
i = 33335
j = 3

(15)
i = 55999
j = 76699

(16)
i = 76699
j = 55999

 Но как сюда попали значения (15) и (16)?

Answer 1

[longclaps]

Ошибка целочисленного переполнения.

55999*76699 == 0x1000186a5  // 33 бита
100005      ==     0x186a5

Answer 2

[Rsa97]

А это у вас вообще не факторизация.
Факторизация - это разложение на простые множители.

Answer 3

[Павел Язовских]

Итого, из остальных двух ответов:
1) пользоваться типом long long (или unsigned long long, если заранее известно, что числа положительные)
2) пробежаться по всем числам от 1 до n, запомнить все простые в список
3) найти все сочетания по 2 с повторами из списка, дающие при умножении n

Comments

[longclaps]

Пользоваться нужно типом longclaps )

Answer 4

[Василий Мельников]

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

Comments

[Павел Язовских]

Можно и делить, но тогда нужно ещё проверять остаток: n%a==0 && n/a==b, чтобы не факторизовать 5 в 2*2

[Василий Мельников]

Павел Язовских, естественно надо проверять иначе как понять делится нацело число или нет

Answer 5

[Wataru]

Немного оффтоп. Для каждого фиксированного i не надо перебирать все j, в поисках того, где i*j=n. Достаточно проверить, что n делится на i без остатка: if (n%i == 0). Тогда j = n/i. Не будет никакого переполнения, которое, как вам longclaps уже ответил(а) привеодит к неверным результатам.

Еще вариант - можно гнать оба цикла до ceil(sqrt(n)). И выводить сразу 2 пары (i,j) и (j,i), если i!=j. потому что из двух множителей хотя бы один не больше корня n, иначе бы перемножение было бы больше n. И еще отдельно надо вывести варианты (1, n) И (n, 1).