File size: 1,684 Bytes
87151cc | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | from math import isqrt
from typing import List
class Primes:
@staticmethod
def is_prime(n: int) -> bool:
"""Check if a number is prime
Args:
n (int): Number to check
Returns:
bool: True if the number is prime, False otherwise
"""
if n < 2:
return False
for i in range(2, isqrt(n) + 1):
if n % i == 0:
return False
return True
@staticmethod
def is_prime_ineff(n: int) -> bool:
"""Check if a number is prime (inefficiently)
Args:
n (int): Number to check
Returns:
bool: True if the number is prime, False otherwise
"""
if n < 2:
return False
for i in range(2, isqrt(n) + 1):
if n % i == 0:
return False
return True
@staticmethod
def sum_primes(n: int) -> int:
"""Sum of primes from 0 to n (exclusive)
Args:
n (int): Number to sum up to
Returns:
int: Sum of primes from 0 to n
"""
sum_ = 0
for i in range(n):
if Primes.is_prime(i):
sum_ += i
return sum_
@staticmethod
def prime_factors(n: int) -> List[int]:
"""Prime factors of a number
Args:
n (int): Number to factorize
Returns:
List[int]: List of prime factors
"""
ret = []
while n > 1:
for i in range(2, n + 1):
if n % i == 0:
ret.append(i)
n = n // i
break
return ret
|