TheAlgorithms-Python

1
"""
2
The first known prime found to exceed one million digits was discovered in 1999,
3
and is a Mersenne prime of the form 2**6972593 − 1; it contains exactly 2,098,960
4
digits. Subsequently other Mersenne primes, of the form 2**p − 1, have been found
5
which contain more digits.
6
However, in 2004 there was found a massive non-Mersenne prime which contains
7
2,357,207 digits: (28433 * (2 ** 7830457 + 1)).
8

9
Find the last ten digits of this prime number.
10
"""
11

12

13
def solution(n: int = 10) -> str:
14
    """
15
    Returns the last n digits of NUMBER.
16
    >>> solution()
17
    '8739992577'
18
    >>> solution(8)
19
    '39992577'
20
    >>> solution(1)
21
    '7'
22
    >>> solution(-1)
23
    Traceback (most recent call last):
24
        ...
25
    ValueError: Invalid input
26
    >>> solution(8.3)
27
    Traceback (most recent call last):
28
        ...
29
    ValueError: Invalid input
30
    >>> solution("a")
31
    Traceback (most recent call last):
32
        ...
33
    ValueError: Invalid input
34
    """
35
    if not isinstance(n, int) or n < 0:
36
        raise ValueError("Invalid input")
37
    modulus = 10**n
38
    number = 28433 * (pow(2, 7830457, modulus)) + 1
39
    return str(number % modulus)
40

41

42
if __name__ == "__main__":
43
    from doctest import testmod
44

45
    testmod()
46
    print(f"{solution(10) = }")
47