The Biggest Prime
February 8, 2013
This is a simple program:
> (with-output-to-file "bigprime.txt"
(lambda ()
(display (- (expt 2 57885161) 1))))
However, when I ran that program, the machine thrashed for a while, and after about a minute, crashed. So I wrote this program using C/GMP, which can be compiled with the command gcc bigprime.c -lgmp -o bigprime:
/* bigprime.c -- save the digits of 2^57885161-1 to a file */
#include
#include "gmp.h"
void main(void)
{
mpz_t p;
FILE *fp;
fp = fopen("bigprime.txt","w");
mpz_init(p);
mpz_ui_pow_ui(p, 2, 57885161);
mpz_sub_ui(p, p, 1);
gmp_fprintf(fp, "%Zd", p);
mpz_clear(p);
fclose(fp);
}
The program ran successfully, creating the bigprime.txt file in about a minute. You can see the program at http://programmingpraxis.codepad.org/xbg11nxk.
Programming Praxis 
From the command line:
redirect to a file if you’d like. Produces 17,425,171 digits in under 5 seconds on my machine.
Using the Pari backend requires raising the Pari stacksize — I didn’t try it. Using the default Calc backend is quite slow as expected with very big numbers — I killed it after 7 minutes.
Fabrice Bellard’s solution to a smaller Mersene can be found here : http://bellard.org/mersenne.html
[…] Pages: 1 2 […]
Haskell:
The first attempt using Python 2.7 failed. It is no problem to make the prime, but printing it (or converting it to a string) takes more than 2 hours (and maybe never finishes). Using the gmpy library the time taken is 22 secs. It creates a file of about 17 MB.
import gmpy out = open("bigprime.txt", "w") n = gmpy.mpz(2 ** 57885161 - 1) out.write("{}".format(n)) out.close()[…] ¿cuáles son todas las cifras del primo 48 de Mersenne? En erl sitio Programming Praxis se reta a los lectores (programadores) a que generen los 17 millones de dígitos. Un programa […]
[…] el sitio https://programmingpraxis.com/2013/02/08/the-biggest-prime han publicado un reto para escribir los un poco más de 17 millones de dígitos que tiene el 48o […]
I had to use the GMP C Library.
There exists a function to specifically do this sort of thing. Here is my code in C :
#include <gmp.h> int main(){ mpz_t one; mpz_t op1; long op2 = 57885161 ; mpz_t temp; mpz_t result; mpz_init(one); mpz_init(result); mpz_init(temp); mpz_init(op1); mpz_set_ui(op1, 1); mpz_set_ui(one, 1); mpz_mul_2exp(temp , op1, op2); mpz_sub(result , temp, one); gmp_printf("The biggest prime number is \n %Zd\n " , result );Redirecting the big prime to a file produces a 16.6 Mb file on my machine. It runs in under 3 seconds on my old laptop with a Pentium 4 processor.
I decided to print it in hex. (-:
What I found out today is that Standard ML’s big integer library appears to be horrifically slow.
The code is:
[sourrcecode]
Control.Print.intinfDepth := 17500000;
IntInf.pow (LargeInt.fromInt 2, 57885161) – 1;
[/sourcecode]
It’s still running after about 5 hours.
[…] trying to solve the biggest prime programming praxis problem in C#. The problem is simple, print out or write to file the number: […]
Globules said
February 9, 2013 at 8:07 AM
Haskell: 1 main = print $ 2^57885161-1
581887266232246442….. Wrong!!