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