How to get decimal form of largest known prime?

[Tim Peters]

[Irmen de Jong]
> In fact, what algorithm is Python itself using when you try to:
>
>  >>> print 2**24036583 - 1
>
> ??

Recent Pythons convert to base 10000 internally by repeated division, along
the lines of

# Convert integer i > 0 to decimal string.
result = []
while i:
    i, digit = divmod(i, 10000)
    s = str(digit)
    if len(s) < 4 and i:
        s = "0" * (4 - len(s)) + s
    result.append(s)
result.reverse()
return "".join(result)

That's an approximation.  The C code doesn't actually build a list, or
reverse it, or do a join(), and does the repeated divisions in a single,
reused memory area.  See long_format() in longobject.c for details.

Older Pythons did much the same, but with base 10, and allocated fresh
memory for each little division.

Both methods are quadratic-time, but modern Pythons do a fourth the number
of "little long division" steps.  By "little" I mean that Python's longs are
represented in base 2**15 internally, so division by 10000 is division by a
single internal digit, which is especially simple.  It's as cheap to divide
a long by 10000 as by 10 -- they're both "single digit" divisors internally.