C ++, целочисленное переполнение?

Question

Я сделал программу, чтобы найти факторы числа:

#include <iostream>
#include <cmath>
using namespace::std;
int main() {
    long int n = 6008514751432;
    int i = 1;
    while (i <= n/2) {
        if (n % i == 0)
            cout << i << " ";
        i++;
    }
}

Я использую xCode BTW. Он отлично работает с меньшими числами, например, скажем, 2000 или даже 200000. Но когда я получаюдо 6008514751432, это число, которое мне нужно знать, оно не работает, оно просто говорит, что программа работает и ничего не отображает!Что происходит?

Обновление: когда я запускаю программу и жду около 2 минут, она говорит:

Warning: the current language does not match this frame.
Current language:  auto; currently c++
(gdb) 

Answer 1

long int, вероятно, имеет ширину 4 байта в вашей реализации, что означает, что он может хранить значения только до 2^31 - 1 или 2147483647.

Вы можете попробовать переключиться на long long, который обычно больше (8 байт на большинстве платформ):

long long n = 6008514751432LL;
long long i = 1LL;
while (i <= n/2) {
    if (n % i == 0)
        cout << i << " ";
    i++;
}

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

Answer 2

В зависимости от вашей платформы, вы обнаружите, что 6008514751432 слишком велик для типа long int. Вы должны убедиться, что вы используете тип, который содержит 64-битный целочисленный тип.

Кроме того, если вы просто пытаетесь найти факторы числа, нет необходимости выглядеть выше, чем sqrt(n), так как факторы больше, чем те, у которых соответствующий коэффициент меньше. Убедитесь, что sqrt вне самой петли.

В системе, где long int больше, чем int, обратите внимание, что в какой-то момент i обернется до 0

Answer 3

Если он работает, он, вероятно, не является целочисленным переполнением в этом конкретном случае.

6008514751432/2, поскольку 32-разрядное целое число получается отрицательным (-144495672), поэтому цикл while будет немедленно завершен.

Целочисленное переполнение порождает неопределенное поведение, поэтому может произойти все что угодно, но большинство систем ведут себя предсказуемо

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

Половина из 6008514751432 все еще довольно велика, и для подсчета этого высокого значения и выполнения всех этих «%» операций потребуется значительное время.Между тем первые несколько факторов (1,2,4,8,1307,2614 и т. Д.) Были отправлены в COUT, но еще не сброшены, поэтому эти результаты находятся в буфере, где вы их не видите.

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

Я предлагаю вам искать более быстрый факторингалгоритм.

Спойлер: FWIW 6008514751432 имеет простые множители

Answer 4

Вы предполагаете, что long int больше, чем есть.Вам следует попробовать следующее:

• print n после того, как вы его присвоили
• print sizeof(int), sizeof(long long)
• , использовать int64_t илайк.int, long и другие не лучший выбор, когда фактический размер имеет значение.
• Добавьте чтение из stdin в свой цикл, попробуйте отладить шаг за шагом, если проблемы сохраняются