TheAlgorithms-Python

1
"""
2
Project Euler Problem 7: https://projecteuler.net/problem=7
3

4
10001st prime
5

6
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we
7
can see that the 6th prime is 13.
8

9
What is the 10001st prime number?
10

11
References:
12
    - https://en.wikipedia.org/wiki/Prime_number
13
"""
14

15
import itertools
16
import math
17

18

19
def is_prime(number: int) -> bool:
20
    """Checks to see if a number is a prime in O(sqrt(n)).
21
    A number is prime if it has exactly two factors: 1 and itself.
22
    Returns boolean representing primality of given number (i.e., if the
23
    result is true, then the number is indeed prime else it is not).
24

25
    >>> is_prime(2)
26
    True
27
    >>> is_prime(3)
28
    True
29
    >>> is_prime(27)
30
    False
31
    >>> is_prime(2999)
32
    True
33
    >>> is_prime(0)
34
    False
35
    >>> is_prime(1)
36
    False
37
    """
38

39
    if 1 < number < 4:
40
        # 2 and 3 are primes
41
        return True
42
    elif number < 2 or number % 2 == 0 or number % 3 == 0:
43
        # Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
44
        return False
45

46
    # All primes number are in format of 6k +/- 1
47
    for i in range(5, int(math.sqrt(number) + 1), 6):
48
        if number % i == 0 or number % (i + 2) == 0:
49
            return False
50
    return True
51

52

53
def prime_generator():
54
    """
55
    Generate a sequence of prime numbers
56
    """
57

58
    num = 2
59
    while True:
60
        if is_prime(num):
61
            yield num
62
        num += 1
63

64

65
def solution(nth: int = 10001) -> int:
66
    """
67
    Returns the n-th prime number.
68

69
    >>> solution(6)
70
    13
71
    >>> solution(1)
72
    2
73
    >>> solution(3)
74
    5
75
    >>> solution(20)
76
    71
77
    >>> solution(50)
78
    229
79
    >>> solution(100)
80
    541
81
    """
82
    return next(itertools.islice(prime_generator(), nth - 1, nth))
83

84

85
if __name__ == "__main__":
86
    print(f"{solution() = }")
87