Source code for titan_pylib.math.divisors
1from collections import Counter
2
3
[docs]
4class Osa_k:
5 """高速素因数分解
6 init: O(NloglogN)
7 N個の数の素因数分解 : O(NlogA)
8 """
9
10 def __init__(self, n: int) -> None:
11 _min_factor = list(range(n + 1))
12 for i in range(2, int(n**0.5) + 1):
13 if _min_factor[i] == i:
14 for j in range(2, int(n // i) + 1):
15 if _min_factor[i * j] > i:
16 _min_factor[i * j] = i
17 self._min_factor = _min_factor
18
[docs]
19 def p_factorization(self, n: int) -> list[int]:
20 ret = []
21 _min_factor = self._min_factor
22 while n > 1:
23 ret.append(_min_factor[n])
24 n //= _min_factor[n]
25 return ret
26
[docs]
27 def p_factorization_Counter(self, n: int) -> Counter:
28 ret = Counter()
29 _min_factor = self._min_factor
30 while n > 1:
31 ret[_min_factor[n]] += 1
32 n //= _min_factor[n]
33 return ret
34
[docs]
35 def get_divisors(self, n: int) -> set:
36 def dfs(indx, val):
37 nonlocal f, m, ret
38 k, v = f[indx]
39 if indx + 1 < m:
40 for i in range(v + 1):
41 dfs(indx + 1, val * k**i)
42 else:
43 for i in range(v + 1):
44 ret.add(val * k**i)
45
46 f = list(self.p_factorization_Counter(n).items())
47 m = len(f)
48 ret = set()
49 dfs(0, 1)
50 return ret
51
52
[docs]
53def get_divisors(n: int) -> list[int]:
54 """約数全列挙. / O(√N)"""
55 l = []
56 r = []
57 for i in range(1, int(n**0.5) + 1):
58 if n % i == 0:
59 l.append(i)
60 if i != n // i:
61 r.append(n // i)
62 return l + r[::-1]
63
64
[docs]
65def factorization(n: int) -> list[tuple[int, int]]:
66 "Nを1回素因数分解する / O(√N)"
67 ret = []
68 if n == 1:
69 return ret
70 for i in range(2, int(-(-(n**0.5) // 1)) + 1):
71 if n == 1:
72 break
73 if n % i == 0:
74 cnt = 0
75 while n % i == 0:
76 cnt += 1
77 n //= i
78 ret.append((i, cnt))
79 if n != 1:
80 ret.append((n, 1))
81 return ret
82
83
[docs]
84def factorization_counter(n: int) -> Counter:
85 "Nを1回素因数分解する / O(√N)"
86 ret = Counter()
87 if n == 1:
88 return ret
89 for i in range(2, int(-(-(n**0.5) // 1)) + 1):
90 if n == 1:
91 break
92 if n % i == 0:
93 cnt = 0
94 while n % i == 0:
95 cnt += 1
96 n //= i
97 ret[i] = cnt
98 if n != 1:
99 ret[n] = 1
100 return ret
101
102
[docs]
103def divisors_num(n: int) -> int:
104 "Nの約数の個数を求める / O(√N)"
105 cnt = 0
106 for i in range(1, int(n**0.5) + 1):
107 if n % i == 0:
108 cnt += 1
109 if i != n // i:
110 cnt += 1
111 return cnt
112
113
[docs]
114def divisors_num_all(n) -> list[int]:
115 "N以下のそれぞれの数の約数の個数を求める / O(NlogN)"
116 li = [0] * (n + 1)
117 for i in range(1, n + 1):
118 for j in range(i, n + 1, i):
119 li[j] += 1
120 return li
121
122
[docs]
123def primefactor_num(n) -> list[int]:
124 "N以下のそれぞれの数の素因数の種類数を求める / O(NloglogN)"
125 cnt = [0] * (n + 1)
126 for i in range(2, n + 1):
127 if cnt[i] >= 1:
128 continue
129 for j in range(i, n + 1, i):
130 cnt[j] += 1
131 return cnt
132
133
[docs]
134def get_primelist(limit: int) -> list[int]:
135 "エラトステネスの篩(N以下の素数を返す) / O(NloglogN)"
136 p = [1] * (limit + 1)
137 p[0] = 0
138 p[1] = 0
139 for i in range(2, int(limit**0.5) + 1):
140 if not p[i]:
141 continue
142 for j in range(i + i, limit + 1, i):
143 p[j] = 0
144 return [i for i, x in enumerate(p) if x]
145
146
[docs]
147def get_prime_count(limit: int) -> int:
148 "N以下の素数の個数を求める / O(NloglogN)"
149 ret = 0
150 for i in range(2, limit):
151 for j in range(2, int(limit**0.5) + 1):
152 if i % j == 0:
153 break
154 else:
155 ret += 1
156 return ret
157
158
[docs]
159def factorization_eratos(n: int, primes: list[int]) -> list[int]:
160 "事前にエラトステネスとかでsart(N)以下の素数を全列挙しておく"
161 "O(sqrt(N)log(log(sqrt(N)) + log(N))"
162 res = []
163 for p in primes:
164 # if is_prime64(n): break
165 if p * p > n:
166 break
167 if n % p == 0:
168 n //= p
169 while n % p == 0:
170 n //= p
171 res.append(p)
172 if n != 1:
173 res.append(n)
174 return res