CODEWITHSUNDEEP
pythonlargenumber
ChaseLouisPowers
ChaseLouisPowers

Reputation: 765

How to calculate and save the largest known prime number?

How can I calculate and save 2^74,207,281 − 1 to a text file?

First problem: I get memory errors when I try to print it. How can I determine how much memory I need?

Second problem: How can I calculate it in the fastest time?

Upvotes: 0

Views: 256

Answers (2)

Spacedman
Spacedman

Reputation: 94222

This calculation is pretty fast for me, doesn't give memory errors and is exact:

>>> x = 2**74207281 - 1

Since:

>>> x > 2**74207281
False
>>> x > 2**74207281 - 2
True

Just don't try and print it out, that will take ages. Try printing small big numbers to get an idea of how long...

Oh, you want to print it out...

The gmpy package has a faster stringification algorithm for its numbers:

>>> x = 2**74207281 - 1
>>> import gmpy
>>> xx = gmpy.mpz(x)
>>> s = str(xx) # takes a few seconds.
>>> len(s)
22338618
>>> f = file("/tmp/bigprime.txt","w")
>>> f.write(s)
>>> f.close()

The resulting file has 22 million digits:

$ wc -c /tmp/bigprime.txt 
22338618 /tmp/bigprime.txt

Upvotes: 5

John Coleman
John Coleman

Reputation: 51998

The function pow() will use exponentiation by squaring and is almost instant:

>>> import math
>>> p = pow(2, 74207281) - 1
>>> math.log10(p)
22338617.477665834

It thus has 22338618 digits.

Upvotes: 2

Related Questions