iframe-proxy | Sunbelt Computer Software

History

84 lines (68 loc) · 1.76 KB

Raw

"""

Project Euler Problem 7: https://projecteuler.net/problem=7

10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we

can see that the 6th prime is 13.

What is the 10001st prime number?

References:

- https://en.wikipedia.org/wiki/Prime_number

"""

from math import sqrt

def is_prime(number: int) -> bool:

"""Checks to see if a number is a prime in O(sqrt(n)).

A number is prime if it has exactly two factors: 1 and itself.

Returns boolean representing primality of given number (i.e., if the

result is true, then the number is indeed prime else it is not).

>>> is_prime(2)

True

>>> is_prime(3)

True

>>> is_prime(27)

False

>>> is_prime(2999)

True

>>> is_prime(0)

False

>>> is_prime(1)

False

"""

if 1 < number < 4:

# 2 and 3 are primes

return True

elif number < 2 or number % 2 == 0 or number % 3 == 0:

# Negatives, 0, 1, all even numbers, all multiples of 3 are not primes

return False

# All primes number are in format of 6k +/- 1

for i in range(5, int(sqrt(number) + 1), 6):

if number % i == 0 or number % (i + 2) == 0:

return False

return True

def solution(nth: int = 10001) -> int:

"""

Returns the n-th prime number.

>>> solution(6)

>>> solution(1)

>>> solution(3)

>>> solution(20)

>>> solution(50)

229

>>> solution(100)

541

"""

count = 0

number = 1

while count != nth and number < 3:

number += 1

if is_prime(number):

count += 1

while count != nth:

number += 2

if is_prime(number):

count += 1

return number

if __name__ == "__main__":

print(f"{solution() = }")

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

sol1.py

Latest commit

History

sol1.py

File metadata and controls