Coverage for src/algolib/maths/number_theory/prime.py: 100%

1from __future__ import annotations 

2import math 

3from algolib.exceptions import InvalidTypeError, InvalidValueError 

4 

5__all__ = ["is_prime"] 

6 

7def is_prime(n: int) -> bool: 

8 r"""Check whether an integer is a prime using the :math:`6k \pm 1` optimization. 

9 

10 Parameters 

11 ---------- 

12 n : int 

13 Non-negative integer to test. 

14 

15 Returns 

16 ------- 

17 bool 

18 True if `n` is prime; False otherwise. 

19 

20 Raises 

21 ------ 

22 InvalidTypeError 

23 If `n` is not int. 

24 InvalidValueError 

25 If `n` is negative. 

26 """ 

27 if not isinstance(n, int): 

28 raise InvalidTypeError(f"n must be int, got {type(n).__name__}") 

29 if n < 0: 

30 raise InvalidValueError(f"n must be non-negative, got {n}") 

31 if n < 2: 

32 return False 

33 if n < 4: 

34 return True 

35 if n % 2 == 0 or n % 3 == 0: 

36 return False 

37 limit = math.isqrt(n) 

38 i = 5 

39 while i <= limit: 

40 if n % i == 0 or n % (i + 2) == 0: 

41 return False 

42 i += 6 

43 return True 

44