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
from math import sqrt
16

17

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

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

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

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

51

52
def solution(nth: int = 10001) -> int:
53
    """
54
    Returns the n-th prime number.
55

56
    >>> solution(6)
57
    13
58
    >>> solution(1)
59
    2
60
    >>> solution(3)
61
    5
62
    >>> solution(20)
63
    71
64
    >>> solution(50)
65
    229
66
    >>> solution(100)
67
    541
68
    """
69

70
    count = 0
71
    number = 1
72
    while count != nth and number < 3:
73
        number += 1
74
        if is_prime(number):
75
            count += 1
76
    while count != nth:
77
        number += 2
78
        if is_prime(number):
79
            count += 1
80
    return number
81

82

83
if __name__ == "__main__":
84
    print(f"{solution() = }")
85