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. >>> is_prime(0) False >>> is_prime(1) False >>> is_prime(2) True >>> is_prime(3) True >>> is_prime(27) False >>> is_prime
(number: int)
| 23 | |
| 24 | |
| 25 | def is_prime(number: int) -> bool: |
| 26 | """Checks to see if a number is a prime in O(sqrt(n)). |
| 27 | |
| 28 | A number is prime if it has exactly two factors: 1 and itself. |
| 29 | |
| 30 | >>> is_prime(0) |
| 31 | False |
| 32 | >>> is_prime(1) |
| 33 | False |
| 34 | >>> is_prime(2) |
| 35 | True |
| 36 | >>> is_prime(3) |
| 37 | True |
| 38 | >>> is_prime(27) |
| 39 | False |
| 40 | >>> is_prime(87) |
| 41 | False |
| 42 | >>> is_prime(563) |
| 43 | True |
| 44 | >>> is_prime(2999) |
| 45 | True |
| 46 | >>> is_prime(67483) |
| 47 | False |
| 48 | """ |
| 49 | |
| 50 | if 1 < number < 4: |
| 51 | # 2 and 3 are primes |
| 52 | return True |
| 53 | elif number < 2 or number % 2 == 0 or number % 3 == 0: |
| 54 | # Negatives, 0, 1, all even numbers, all multiples of 3 are not primes |
| 55 | return False |
| 56 | |
| 57 | # All primes number are in format of 6k +/- 1 |
| 58 | for i in range(5, int(math.sqrt(number) + 1), 6): |
| 59 | if number % i == 0 or number % (i + 2) == 0: |
| 60 | return False |
| 61 | return True |
| 62 | |
| 63 | |
| 64 | odd_composites = [num for num in range(3, 100001, 2) if not is_prime(num)] |
no outgoing calls
no test coverage detected