O fator é muito grande

Question

Estou tentando usar um utilitário factor , mas ele me diz que esse número é muito grande. Existe algum utilitário que possa fazer o que o factor está fazendo, mas não diz que esse número é muito grande?

    

Answer 1

Talvez seu factor não tenha sido criado com GMP , por isso não é possível manipular um número maior que 2**64-1 :

$ factor 18446744073709551616
factor: '18446744073709551616' is too large
$ factor 18446744073709551615
18446744073709551615: 3 5 17 257 641 65537 6700417

Executando este comando para verificar se factor foi criado com GMP :

$ ldd /usr/bin/factor 
        linux-vdso.so.1 (0x00007fffda1fe000)
        libgmp.so.10 => /usr/lib64/libgmp.so.10 (0x00007faae00f5000)
        libc.so.6 => /lib64/libc.so.6 (0x00007faadfd46000)
        /lib64/ld-linux-x86-64.so.2 (0x00007faae037c000)

O limite pode ser maior em algumas máquinas (o número tem que caber no tipo uintmax_t ), mas seu número é um número de 256 bits e nenhuma máquina comum suporta tão grande uintmax_t , se houver. / p>

Observe que o utilitário factor pode ser compilado com o suporte GMP . Nesse caso, não há efetivamente nenhum limite no tamanho do número. Parece que sua distribuição não ativou o suporte a GMP (o que faz sentido, já que isso adicionaria uma dependência em uma biblioteca extra a um pacote do sistema principal para um recurso raramente usado).

Se você tem perl , pode experimentar factor.pl program no módulo Math::Prime::Util :

$ /home/cuonglm/.cpan/build/Math-Prime-Util-0.31-9c_xq3/bin/factor.pl 115792089237316195423570985008687907852837564279074904382605163141518161494337
115792089237316195423570985008687907852837564279074904382605163141518161494337: 115792089237316195423570985008687907852837564279074904382605163141518161494337

    

Answer 2

Você também pode usar factor dos coreutils. No entanto, ele precisa ser compilado com suporte bignum. FYI, este não é o caso com o binário que vem com algumas distribuições, como o Debian ( bug 608832 ). Mas você pode baixar o código-fonte e recompilá-lo depois de instalar o GMP (que é usado por padrão se encontrado).

Outra solução é usar Pari / GP (bem conhecido pela teoria dos números):

? factor(806578020551755900412008880903137528217525975284037923)
%1 =
[ 238366085426200783161668947 1]

[3383778439410064898661524209 1]

Com esse número, leva alguns segundos.