blob: 87379a1b3a6c446aed1608c94c8f9ea1e888f5a5 (
plain)
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
|
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys
from typing import List
def prime_decomposition(n: int) -> List[int]:
"""
Compute the prime factors of a number.
Args:
n: An integer greater than or equal to 2.
Returns:
A list of prime factors of the input number.
Raises:
ValueError: If the input number is less than 2.
"""
if n < 2:
raise ValueError("Number should be greater than or equal to 2")
factors = []
d = 2
# Divide the number by prime factors
while n > 1:
while n % d == 0:
factors.append(d)
n //= d
d += 1
if d * d > n and n > 1:
factors.append(n)
break
return factors
# Test cases
def test_prime_decomposition():
assert prime_decomposition(228) == [2, 2, 3, 19]
assert prime_decomposition(131) == [131]
assert prime_decomposition(101) == [101]
try:
prime_decomposition(1)
except ValueError:
pass
else:
assert False, "Expected ValueError for input 1"
if __name__ == '__main__':
# Parse command line argument
if len(sys.argv) != 2:
print(f"Usage: {sys.argv[0]} <number>")
sys.exit(1)
n = int(sys.argv[1])
# Compute the prime decomposition
factors = prime_decomposition(n)
# Print the prime factors
print(", ".join(str(f) for f in factors))
# Run tests
test_prime_decomposition()
|
