prime factors Algorithm
In abstract algebra, objects that behave in a generalized manner like prime numbers include prime components and prime ideals. A prime number (or a prime) is a natural number greater than 1 that is not a merchandise of two smaller natural numbers. method that are restricted to specific number forms include Pépin's test for Fermat numbers (1877), Proth's theorem (c. 1878), the Lucas – Lehmer primality test (originated 1856), and the generalized Lucas primality test.
"""
python/black : True
"""
from typing import List
def prime_factors(n: int) -> List[int]:
"""
Returns prime factors of n as a list.
>>> prime_factors(0)
[]
>>> prime_factors(100)
[2, 2, 5, 5]
>>> prime_factors(2560)
[2, 2, 2, 2, 2, 2, 2, 2, 2, 5]
>>> prime_factors(10**-2)
[]
>>> prime_factors(0.02)
[]
>>> x = prime_factors(10**241) # doctest: +NORMALIZE_WHITESPACE
>>> x == [2]*241 + [5]*241
True
>>> prime_factors(10**-354)
[]
>>> prime_factors('hello')
Traceback (most recent call last):
...
TypeError: '<=' not supported between instances of 'int' and 'str'
>>> prime_factors([1,2,'hello'])
Traceback (most recent call last):
...
TypeError: '<=' not supported between instances of 'int' and 'list'
"""
i = 2
factors = []
while i * i <= n:
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return factors
if __name__ == "__main__":
import doctest
doctest.testmod()
