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 인 계승.

자신 만의 bignum 라이브러리를 재발견하지 마십시오. 복잡한 기본 알고리즘 (순진 알고리즘보다 효율적)은 이해하기 어렵고 (다시 발명하기가) 어렵 기 때문입니다.

일부 언어 및 구현 (예 : Common Lisp의 경우 SBCL)에는 bignum이 내장되어 있습니다.