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