Функции с очень большими числами в C++

Question

Я довольно новичок в C++ и пытаюсь написать программу для обработки очень больших входных чисел (7e + 11 ish). Он отлично работает с небольшими количествами, но не с этими большими. Я понимаю, это потому, что очень большие числа не будут вписываться в int, но когда я пытаюсь использовать другие типы, такие как __int64, long long int, unsigned long long int и uint64_t, функция «nextsmallestfactor» не работает (обычно она выдает 0 и поэтому срабатывает ошибка при делении на a, на выходе). Что мне тогда использовать? Этот код должен принимать большое число, многократно делить его на наименьшее число, которое делится на него каждый раз, и вывести a, самый высокий основной коэффициент, в конце.

#include <iostream> 
using namespace std; 

int numberToFactorise = 700000000000; 
int nextsmallestfactor(int numbertofactorise){ 
    for (int factor = 2; factor < numbertofactorise; factor++){ 
    if (numbertofactorise%factor == 0){ 
     return factor; 
    } 
} 
} 
int main(){ 
    int quotient = numberToFactorise; 
    int a=1; 
    while (quotient > 1){ 
     a = nextsmallestfactor(quotient); 
     quotient = quotient/a; 
    }; 
    cout << a; 
cout << endl; 
system("PAUSE"); 
return 0; 

}

Большое спасибо за любую помощь.

Answer 1

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

nextsmallestfactor(5): 

     factor | numbertofactorise % factor 
     ---------------------------- 
     2  | 5%2 = 1 
     3  | 5%3 = 2 
     4  | 5%4 = 1 

END (no return) 

Если изменить условную для проверки коэффициента до включительно в numbertofactorize тогда он будет делать:

nextsmallestfactor(5): 

     factor | numbertofactorise % factor 
     ---------------------------- 
     2  | 5%2 = 1 
     3  | 5%3 = 2 
     4  | 5%4 = 1 
     5  | 5%5 = 0 ---> return 5; 

Answer 2

Если вы хотите написать код C++, способный обрабатывать огромные числа (со всеми их цифрами), вам нужно bignums. Затем я предлагаю вам использовать некоторую существующую библиотеку bignum, такую ​​как GMPLIB; вы сможете вычислить, например. факториал 1000 со всеми его цифрами.

Не пытайтесь изобретать собственную библиотеку бигума; так как сложные базовые алгоритмы (более эффективные, чем наивные) довольно трудно понять (и вновь изобретать).

Некоторые языки и реализации (например, SBCL для Common Lisp) имеют встроенные бонусы.