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

Я сделал программу для нахождения множителей числа:

#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)

c++ integer-overflow
person Billjk    schedule 07.03.2012    source источник
comment
Обратите внимание на время выполнения вашего алгоритма...   -  person Mysticial    schedule 07.03.2012
comment
Какой компилятор вы используете? В Visual C++ long ints и ints занимают одинаковый объем памяти, поэтому они имеют одинаковый целочисленный диапазон.   -  person In silico    schedule 07.03.2012
comment
он просто говорит, что программа запущена и ничего не отображает! К сожалению, он говорит вам правду.   -  person Sergey Kalinichenko    schedule 07.03.2012

Ответы (4)


arrow_upward
2
arrow_downward

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

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

Обратите внимание, что в системе, где long int больше, чем int, вы обнаружите, что в какой-то момент i преобразуется в 0.

person Keith    schedule 07.03.2012
comment
Что это за тип, который вмещает так много? - person Billjk; 07.03.2012
comment
@ user1247509: long long — это 64-битный целочисленный тип со знаком, который вы можете использовать в компиляторах, которые его поддерживают. Я рекомендую вам использовать long long, если вы можете. - person In silico; 07.03.2012
comment
обычно long long или _int64 в windows. - person Jonathan Henson; 07.03.2012
comment
long long является частью C++11, IIRC. - person Etienne de Martel; 13.03.2012

arrow_upward
3
arrow_downward

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.

person Etienne de Martel    schedule 07.03.2012

arrow_upward
1
arrow_downward

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

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

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

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

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

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

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

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

2 2 2 1307 574647547

person Jasen    schedule 09.02.2013

arrow_upward
0
arrow_downward

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

  • распечатайте n после того, как вы его присвоили
  • напечатать sizeof(int), sizeof(long long)
  • используйте int64_t и тому подобное. int, long и другие - не лучший выбор, когда важен фактический размер.
  • Добавьте чтение со стандартного ввода в свой цикл, попробуйте и отладьте шаг за шагом, если проблемы не исчезнут.
person J.N.    schedule 07.03.2012