

"""simple docstring"""


from __future__ import annotations

import math
import random






def 					a__					(					__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE				)			->			list[int]:
		__lowerCAmelCase: Tuple					   =    d * e - 1
		__lowerCAmelCase: Any					   =    0
		__lowerCAmelCase: Optional[Any]					   =    0
		while p == 0:
				__lowerCAmelCase: Dict					   =    random.randint(2      ,				n - 1				)
				__lowerCAmelCase: int					   =    k
				while True:
						if t % 2 == 0:
								__lowerCAmelCase: List[str]					   =    t // 2
								__lowerCAmelCase: Tuple					   =    (g**t) % n
								__lowerCAmelCase: Dict					   =    math.gcd(x - 1      ,				__SCREAMING_SNAKE_CASE				)
								if x > 1 and y > 1:
										__lowerCAmelCase: List[Any]					   =    y
										__lowerCAmelCase: Optional[Any]					   =    n // y
										break  # find the correct factors
						else:
								break  # t is not divisible by 2, break and choose another g
		return sorted([p, q]				)


if __name__ == "__main__":
			import doctest

			doctest.testmod()





"""simple docstring"""


import math






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			list:
		if n <= 0:
				raise ValueError("Only positive integers have prime factors"				)
		__lowerCAmelCase: Tuple					   =    []
		while n % 2 == 0:
				pf.append(2				)
				__lowerCAmelCase: str					   =    int(n / 2				)
		for i in range(3      ,				int(math.sqrt(__SCREAMING_SNAKE_CASE				)				) + 1      ,				2				):
				while n % i == 0:
						pf.append(__SCREAMING_SNAKE_CASE				)
						__lowerCAmelCase: List[Any]					   =    int(n / i				)
		if n > 2:
				pf.append(__SCREAMING_SNAKE_CASE				)
		return pf






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			int:
		if n <= 0:
				raise ValueError("Only positive numbers are accepted"				)
		__lowerCAmelCase: int					   =    1
		__lowerCAmelCase: str					   =    1
		while n % 2 == 0:
				temp += 1
				__lowerCAmelCase: Dict					   =    int(n / 2				)
		div *= temp
		for i in range(3      ,				int(math.sqrt(__SCREAMING_SNAKE_CASE				)				) + 1      ,				2				):
				__lowerCAmelCase: int					   =    1
				while n % i == 0:
						temp += 1
						__lowerCAmelCase: Tuple					   =    int(n / i				)
				div *= temp
		if n > 1:
				div *= 2
		return div






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			int:
		if n <= 0:
				raise ValueError("Only positive numbers are accepted"				)
		__lowerCAmelCase: Dict					   =    1
		__lowerCAmelCase: int					   =    1
		while n % 2 == 0:
				temp += 1
				__lowerCAmelCase: Tuple					   =    int(n / 2				)
		if temp > 1:
				s *= (2**temp - 1) / (2 - 1)
		for i in range(3      ,				int(math.sqrt(__SCREAMING_SNAKE_CASE				)				) + 1      ,				2				):
				__lowerCAmelCase: List[Any]					   =    1
				while n % i == 0:
						temp += 1
						__lowerCAmelCase: List[str]					   =    int(n / i				)
				if temp > 1:
						s *= (i**temp - 1) / (i - 1)
		return int(__SCREAMING_SNAKE_CASE				)






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			int:
		__lowerCAmelCase: Optional[int]					   =    n
		for x in set(prime_factors(__SCREAMING_SNAKE_CASE				)				):
				s *= (x - 1) / x
		return int(__SCREAMING_SNAKE_CASE				)


if __name__ == "__main__":
			import doctest

			doctest.testmod()


