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 >>> i
(number: int)
| 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: |