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)
| 15 | |
| 16 | |
| 17 | def is_prime(number: int) -> bool: |
| 18 | """Checks to see if a number is a prime in O(sqrt(n)). |
| 19 | A number is prime if it has exactly two factors: 1 and itself. |
| 20 | Returns boolean representing primality of given number (i.e., if the |
| 21 | result is true, then the number is indeed prime else it is not). |
| 22 | |
| 23 | >>> is_prime(2) |
| 24 | True |
| 25 | >>> is_prime(3) |
| 26 | True |
| 27 | >>> is_prime(27) |
| 28 | False |
| 29 | >>> is_prime(2999) |
| 30 | True |
| 31 | >>> is_prime(0) |
| 32 | False |
| 33 | >>> is_prime(1) |
| 34 | False |
| 35 | """ |
| 36 | |
| 37 | if 1 < number < 4: |
| 38 | # 2 and 3 are primes |
| 39 | return True |
| 40 | elif number < 2 or number % 2 == 0 or number % 3 == 0: |
| 41 | # Negatives, 0, 1, all even numbers, all multiples of 3 are not primes |
| 42 | return False |
| 43 | |
| 44 | # All primes number are in format of 6k +/- 1 |
| 45 | for i in range(5, int(math.sqrt(number) + 1), 6): |
| 46 | if number % i == 0 or number % (i + 2) == 0: |
| 47 | return False |
| 48 | return True |
| 49 | |
| 50 | |
| 51 | def solution(n: int = 600851475143) -> int: |