



from math import sqrt

def        a						(      _UpperCAmelCase							:					Optional[int]						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (
		    number >= 0
		), "'number' must been an int and positive"

		__UpperCAmelCase    :     Optional[int]													=	True

		# 0 and 1 are none primes.
		if number <= 1:
				__UpperCAmelCase    :     List[Any]													=	False

		for divisor in range(2 ,   int(round(sqrt(_UpperCAmelCase						)						)						) + 1						):
				# if 'number' divisible by 'divisor' then sets 'status'
				# of false and break up the loop.
				if number % divisor == 0:
						__UpperCAmelCase    :     Union[str, Any]													=	False
						break

    # precondition
		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						), "'status' must been from type bool"

		return status

def        a						(      _UpperCAmelCase							:					int						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (n > 2), "'N' must been an int and > 2"

		# beginList: contains all natural numbers from 2 up to N
		__UpperCAmelCase    :     List[str]													=	list(range(2 ,   n + 1						)						)

		__UpperCAmelCase    :     Tuple													=	[]  # this list will be returns.

		# actual sieve of erathostenes
		for i in range(len(_UpperCAmelCase						)						):
				for j in range(i + 1 ,   len(_UpperCAmelCase						)						):
						if (begin_list[i] != 0) and (begin_list[j] % begin_list[i] == 0):
								__UpperCAmelCase    :     List[Any]													=	0

    # filters actual prime numbers.
		__UpperCAmelCase    :     str													=	[x for x in begin_list if x != 0]

		# precondition
		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						), "'ans' must been from type list"

		return ans

def        a						(      _UpperCAmelCase							:					Optional[Any]						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (n > 2), "'N' must been an int and > 2"

		__UpperCAmelCase    :     List[str]													=	[]

		# iterates over all numbers between 2 up to N+1
		# if a number is prime then appends to list 'ans'
		for number in range(2 ,   n + 1						):
				if is_prime(_UpperCAmelCase						):
						ans.append(_UpperCAmelCase						)

    # precondition
		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						), "'ans' must been from type list"

		return ans

def        a						(      _UpperCAmelCase							:					Union[str, Any]						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and number >= 0, "'number' must been an int and >= 0"

		__UpperCAmelCase    :     Dict													=	[]  # this list will be returns of the function.

		# potential prime number factors.

		__UpperCAmelCase    :     Union[str, Any]													=	2

		__UpperCAmelCase    :     List[str]													=	number

		if number == 0 or number == 1:
				ans.append(_UpperCAmelCase						)

		# if 'number' not prime then builds the prime factorization of 'number'
		elif not is_prime(_UpperCAmelCase						):
				while quotient != 1:
						if is_prime(_UpperCAmelCase						) and (quotient % factor == 0):
								ans.append(_UpperCAmelCase						)
								quotient /= factor
						else:
								factor += 1

		else:
				ans.append(_UpperCAmelCase						)

		# precondition
		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						), "'ans' must been from type list"

		return ans

def        a						(      _UpperCAmelCase							:					List[str]						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (
		    number >= 0
		), "'number' bust been an int and >= 0"

		__UpperCAmelCase    :     int													=	0

		# prime factorization of 'number'
		__UpperCAmelCase    :     List[Any]													=	prime_factorization(_UpperCAmelCase						)

		__UpperCAmelCase    :     Tuple													=	max(_UpperCAmelCase						)

		# precondition
		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						), "'ans' must been from type int"

		return ans

def        a						(      _UpperCAmelCase							:					Dict						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (
		    number >= 0
		), "'number' bust been an int and >= 0"

		__UpperCAmelCase    :     Optional[Any]													=	0

		# prime factorization of 'number'
		__UpperCAmelCase    :     Dict													=	prime_factorization(_UpperCAmelCase						)

		__UpperCAmelCase    :     Dict													=	min(_UpperCAmelCase						)

		# precondition
		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						), "'ans' must been from type int"

		return ans

def        a						(      _UpperCAmelCase							:					str						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						), "'number' must been an int"
		assert isinstance(number % 2 == 0 ,   _UpperCAmelCase						), "compare bust been from type bool"

		return number % 2 == 0

def        a						(      _UpperCAmelCase							:					Any						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						), "'number' must been an int"
		assert isinstance(number % 2 != 0 ,   _UpperCAmelCase						), "compare bust been from type bool"

		return number % 2 != 0

def        a						(      _UpperCAmelCase							:					Union[str, Any]						):







		'''simple docstring'''





		assert (
		    isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (number > 2) and is_even(_UpperCAmelCase						)
		), "'number' must been an int, even and > 2"

		__UpperCAmelCase    :     Dict													=	[]  # this list will returned

		# creates a list of prime numbers between 2 up to 'number'
		__UpperCAmelCase    :     Optional[int]													=	get_prime_numbers(_UpperCAmelCase						)
		__UpperCAmelCase    :     str													=	len(_UpperCAmelCase						)

		# run variable for while-loops.
		__UpperCAmelCase    :     Any													=	0
		__UpperCAmelCase    :     List[str]													=	None

		# exit variable. for break up the loops
		__UpperCAmelCase    :     int													=	True

		while i < len_pn and loop:
				__UpperCAmelCase    :     str													=	i + 1

				while j < len_pn and loop:
						if prime_numbers[i] + prime_numbers[j] == number:
								__UpperCAmelCase    :     Any													=	False
								ans.append(prime_numbers[i]						)
								ans.append(prime_numbers[j]						)

						j += 1

				i += 1

		# precondition
		assert (
		    isinstance(_UpperCAmelCase ,   _UpperCAmelCase						)
		    and (len(_UpperCAmelCase						) == 2)
		    and (ans[0] + ans[1] == number)
		    and is_prime(ans[0]						)
		    and is_prime(ans[1]						)
		), "'ans' must contains two primes. And sum of elements must been eq 'number'"

		return ans

def        a						(      _UpperCAmelCase							:					List[Any] ,   _UpperCAmelCase							:					Optional[Any]						):







		'''simple docstring'''





		assert (
		    isinstance(_UpperCAmelCase ,   _UpperCAmelCase						)
		    and isinstance(_UpperCAmelCase ,   _UpperCAmelCase						)
		    and (numbera >= 0)
		    and (numbera >= 0)
		), "'number1' and 'number2' must been positive integer."

		__UpperCAmelCase    :     Dict													=	0

		while numbera != 0:
				__UpperCAmelCase    :     Union[str, Any]													=	numbera % numbera
				__UpperCAmelCase    :     List[str]													=	numbera
				__UpperCAmelCase    :     Tuple													=	rest

		# precondition
		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (
		    numbera >= 0
		), "'number' must been from type int and positive"

		return numbera

def        a						(      _UpperCAmelCase							:					Tuple ,   _UpperCAmelCase							:					List[Any]						):







		'''simple docstring'''





		assert (
		    isinstance(_UpperCAmelCase ,   _UpperCAmelCase						)
		    and isinstance(_UpperCAmelCase ,   _UpperCAmelCase						)
		    and (numbera >= 1)
		    and (numbera >= 1)
		), "'number1' and 'number2' must been positive integer."

		__UpperCAmelCase    :     str													=	1  # actual answer that will be return.

		# for kgV (x,1)
		if numbera > 1 and numbera > 1:
				# builds the prime factorization of 'number1' and 'number2'
				__UpperCAmelCase    :     Optional[int]													=	prime_factorization(_UpperCAmelCase						)
				__UpperCAmelCase    :     Union[str, Any]													=	prime_factorization(_UpperCAmelCase						)

		elif numbera == 1 or numbera == 1:
				__UpperCAmelCase    :     int													=	[]
				__UpperCAmelCase    :     Any													=	[]
				__UpperCAmelCase    :     str													=	max(_UpperCAmelCase ,   _UpperCAmelCase						)

		__UpperCAmelCase    :     str													=	0
		__UpperCAmelCase    :     str													=	0

		__UpperCAmelCase    :     Any													=	[]  # captured numbers int both 'primeFac1' and 'primeFac2'

		# iterates through primeFac1
		for n in prime_fac_a:
				if n not in done:
						if n in prime_fac_a:
								__UpperCAmelCase    :     Any													=	prime_fac_a.count(_UpperCAmelCase						)
								__UpperCAmelCase    :     Union[str, Any]													=	prime_fac_a.count(_UpperCAmelCase						)

								for _ in range(max(_UpperCAmelCase ,   _UpperCAmelCase						)						):
										ans *= n

						else:
								__UpperCAmelCase    :     int													=	prime_fac_a.count(_UpperCAmelCase						)

								for _ in range(_UpperCAmelCase						):
										ans *= n

						done.append(_UpperCAmelCase						)

    # iterates through primeFac2
		for n in prime_fac_a:
				if n not in done:
						__UpperCAmelCase    :     Union[str, Any]													=	prime_fac_a.count(_UpperCAmelCase						)

						for _ in range(_UpperCAmelCase						):
								ans *= n

						done.append(_UpperCAmelCase						)

    # precondition
		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (
		    ans >= 0
		), "'ans' must been from type int and positive"

		return ans

def        a						(      _UpperCAmelCase							:					Optional[int]						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (n >= 0), "'number' must been a positive int"

		__UpperCAmelCase    :     List[str]													=	0
		__UpperCAmelCase    :     Any													=	2  # this variable holds the answer

		while index < n:
				index += 1

				ans += 1  # counts to the next number

				# if ans not prime then
				# runs to the next prime number.
				while not is_prime(_UpperCAmelCase						):
						ans += 1

    # precondition
		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and is_prime(
		    _UpperCAmelCase						), "'ans' must been a prime number and from type int"

		return ans

def        a						(      _UpperCAmelCase							:					Optional[int] ,   _UpperCAmelCase							:					Optional[Any]						):







		'''simple docstring'''





		assert (
		    is_prime(_UpperCAmelCase						) and is_prime(_UpperCAmelCase						) and (p_number_a < p_number_a)
		), "The arguments must been prime numbers and 'pNumber1' < 'pNumber2'"

		__UpperCAmelCase    :     List[str]													=	p_number_a + 1  # jump to the next number

		__UpperCAmelCase    :     int													=	[]  # this list will be returns.

		# if number is not prime then
		# fetch the next prime number.
		while not is_prime(_UpperCAmelCase						):
				number += 1

		while number < p_number_a:
				ans.append(_UpperCAmelCase						)

				number += 1

				# fetch the next prime number.
				while not is_prime(_UpperCAmelCase						):
						number += 1

    # precondition
		assert (
		    isinstance(_UpperCAmelCase ,   _UpperCAmelCase						)
		    and ans[0] != p_number_a
		    and ans[len(_UpperCAmelCase						) - 1] != p_number_a
		), "'ans' must been a list without the arguments"

		# 'ans' contains not 'pNumber1' and 'pNumber2' !
		return ans

def        a						(      _UpperCAmelCase							:					Optional[int]						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (n >= 1), "'n' must been int and >= 1"

		__UpperCAmelCase    :     Optional[int]													=	[]  # will be returned.

		for divisor in range(1 ,   n + 1						):
				if n % divisor == 0:
						ans.append(_UpperCAmelCase						)

    # precondition
		assert ans[0] == 1 and ans[len(_UpperCAmelCase						) - 1] == n, "Error in function getDivisiors(...)"

		return ans

def        a						(      _UpperCAmelCase							:					List[str]						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (
		    number > 1
		), "'number' must been an int and >= 1"

		__UpperCAmelCase    :     Optional[Any]													=	get_divisors(_UpperCAmelCase						)

		# precondition
		assert (
		    isinstance(_UpperCAmelCase ,   _UpperCAmelCase						)
		    and (divisors[0] == 1)
		    and (divisors[len(_UpperCAmelCase						) - 1] == number)
		), "Error in help-function getDivisiors(...)"

		# summed all divisors up to 'number' (exclusive), hence [:-1]
		return sum(divisors[:-1]						) == number

def        a						(      _UpperCAmelCase							:					List[str] ,   _UpperCAmelCase							:					str						):







		'''simple docstring'''





		assert (
		    isinstance(_UpperCAmelCase ,   _UpperCAmelCase						)
		    and isinstance(_UpperCAmelCase ,   _UpperCAmelCase						)
		    and (denominator != 0)
		), "The arguments must been from type int and 'denominator' != 0"

		# build the greatest common divisor of numerator and denominator.
		__UpperCAmelCase    :     Union[str, Any]													=	gcd(abs(_UpperCAmelCase						) ,   abs(_UpperCAmelCase						)						)

		# precondition
		assert (
		    isinstance(_UpperCAmelCase ,   _UpperCAmelCase						)
		    and (numerator % gcd_of_fraction == 0)
		    and (denominator % gcd_of_fraction == 0)
		), "Error in function gcd(...,...)"

		return (numerator // gcd_of_fraction, denominator // gcd_of_fraction)

def        a						(      _UpperCAmelCase							:					Optional[int]						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (n >= 0), "'n' must been a int and >= 0"

		__UpperCAmelCase    :     Dict													=	1  # this will be return.

		for factor in range(1 ,   n + 1						):
				ans *= factor

		return ans

def        a						(      _UpperCAmelCase							:					Optional[int]						):







		'''simple docstring'''





		assert isinstance(_UpperCAmelCase ,   _UpperCAmelCase						) and (n >= 0), "'n' must been an int and >= 0"

		__UpperCAmelCase    :     Optional[int]													=	0
		__UpperCAmelCase    :     Tuple													=	1
		__UpperCAmelCase    :     Any													=	1  # this will be return

		for _ in range(n - 1						):
				__UpperCAmelCase    :     Optional[int]													=	ans
				ans += fiba
				__UpperCAmelCase    :     Union[str, Any]													=	tmp

		return ans








class   __lowercase				:




			"""simple docstring"""







			def __init__( self  :     List[Any]   ,						lowerCAmelCase__  :     Optional[int]   ,						lowerCAmelCase__  :     List[Any]):
									SCREAMING_SNAKE_CASE_: List[str]  		=       name
									SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       val



			def __str__( self  :     Dict):
									return F"{self.__class__.__name__}({self.name}, {self.val})"




			def __lt__( self  :     List[str]   ,						lowerCAmelCase__  :     Any):
									return self.val < other.val







class   __lowercase				:




			"""simple docstring"""







			def __init__( self  :     Tuple   ,						lowerCAmelCase__  :     Dict):
									SCREAMING_SNAKE_CASE_: str  		=       {}
									SCREAMING_SNAKE_CASE_: int  		=       {}
									SCREAMING_SNAKE_CASE_: Any  		=       self.build_heap(lowerCAmelCase__)



			def __getitem__( self  :     List[Any]   ,						lowerCAmelCase__  :     Dict):
									return self.get_value(lowerCAmelCase__)



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[Any]   ,						lowerCAmelCase__  :     Dict):
									return (idx - 1) // 2



			def        _SCREAMING_SNAKE_CASE			( self  :     Union[str, Any]   ,						lowerCAmelCase__  :     Optional[Any]):
									return idx * 2 + 1



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[int]   ,						lowerCAmelCase__  :     Tuple):
									return idx * 2 + 2



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[int]   ,						lowerCAmelCase__  :     Optional[int]):
									return self.heap_dict[key]



			def        _SCREAMING_SNAKE_CASE			( self  :     List[Any]   ,						lowerCAmelCase__  :     Union[str, Any]):
									SCREAMING_SNAKE_CASE_: Tuple  		=       len(lowerCAmelCase__) - 1
									SCREAMING_SNAKE_CASE_: List[str]  		=       self.get_parent_idx(lowerCAmelCase__)

									for idx, i in enumerate(lowerCAmelCase__):
															SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       idx
															SCREAMING_SNAKE_CASE_: str  		=       i.val

									for i in range(lowerCAmelCase__   ,						-1   ,						-1):
															self.sift_down(lowerCAmelCase__   ,						lowerCAmelCase__)
									return array



			def        _SCREAMING_SNAKE_CASE			( self  :     str   ,						lowerCAmelCase__  :     Optional[int]   ,						lowerCAmelCase__  :     List[str]):
									while True:
															SCREAMING_SNAKE_CASE_: Optional[Any]  		=       self.get_left_child_idx(lowerCAmelCase__)  # noqa: E741
															SCREAMING_SNAKE_CASE_: Dict  		=       self.get_right_child_idx(lowerCAmelCase__)

															SCREAMING_SNAKE_CASE_: int  		=       idx
															if l < len(lowerCAmelCase__) and array[l] < array[idx]:
																					SCREAMING_SNAKE_CASE_: List[str]  		=       l
															if r < len(lowerCAmelCase__) and array[r] < array[smallest]:
																					SCREAMING_SNAKE_CASE_: str  		=       r

															if smallest != idx:
																					SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_: Any  		=       array[smallest], array[idx]
																					(
																					    (
																					    SCREAMING_SNAKE_CASE_
																					)		,    (
																					    SCREAMING_SNAKE_CASE_
																					)		,    
																					): Optional[Any]  		=       (
																					    self.idx_of_element[array[smallest]],
																					    self.idx_of_element[array[idx]],
																					)
																					SCREAMING_SNAKE_CASE_: Optional[int]  		=       smallest
															else:
																					break



			def        _SCREAMING_SNAKE_CASE			( self  :     Dict   ,						lowerCAmelCase__  :     str):
									SCREAMING_SNAKE_CASE_: Any  		=       self.get_parent_idx(lowerCAmelCase__)
									while p >= 0 and self.heap[p] > self.heap[idx]:
															SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_: List[Any]  		=       self.heap[idx], self.heap[p]
															SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_: Tuple  		=       (
															    self.idx_of_element[self.heap[idx]],
															    self.idx_of_element[self.heap[p]],
															)
															SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       p
															SCREAMING_SNAKE_CASE_: Optional[int]  		=       self.get_parent_idx(lowerCAmelCase__)



			def        _SCREAMING_SNAKE_CASE			( self  :     List[Any]):
									return self.heap[0]



			def        _SCREAMING_SNAKE_CASE			( self  :     Dict):
									SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_: Tuple  		=       self.heap[-1], self.heap[0]
									SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_: List[str]  		=       (
									    self.idx_of_element[self.heap[-1]],
									    self.idx_of_element[self.heap[0]],
									)

									SCREAMING_SNAKE_CASE_: int  		=       self.heap.pop()
									del self.idx_of_element[x]
									self.sift_down(0   ,						self.heap)
									return x



			def        _SCREAMING_SNAKE_CASE			( self  :     Union[str, Any]   ,						lowerCAmelCase__  :     Tuple):
									self.heap.append(lowerCAmelCase__)
									SCREAMING_SNAKE_CASE_: List[str]  		=       len(self.heap) - 1
									SCREAMING_SNAKE_CASE_: List[str]  		=       node.val
									self.sift_up(len(self.heap) - 1)



			def        _SCREAMING_SNAKE_CASE			( self  :     List[Any]):
									return len(self.heap) == 0




			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[Any]   ,						lowerCAmelCase__  :     Any   ,						lowerCAmelCase__  :     Optional[int]):
									assert (
									    self.heap[self.idx_of_element[node]].val > new_value
									), "newValue must be less that current value"
									SCREAMING_SNAKE_CASE_: Any  		=       new_value
									SCREAMING_SNAKE_CASE_: Tuple  		=       new_value
									self.sift_up(self.idx_of_element[node])







lowerCAmelCase							:  int   	=						Node("""R""", -1)
lowerCAmelCase							:  str   	=						Node("""B""", 6)
lowerCAmelCase							:  str   	=						Node("""A""", 3)
lowerCAmelCase							:  List[str]   	=						Node("""X""", 1)
lowerCAmelCase							:  Union[str, Any]   	=						Node("""E""", 4)

# Use one of these two ways to generate Min-Heap

# Generating Min-Heap from array
lowerCAmelCase							:  Optional[Any]   	=						MinHeap([r, b, a, x, e])

# Generating Min-Heap by Insert method
# myMinHeap.insert(a)
# myMinHeap.insert(b)
# myMinHeap.insert(x)
# myMinHeap.insert(r)
# myMinHeap.insert(e)

# Before
print("""Min Heap - before decrease key""")
for i in my_min_heap.heap:
						print(i)

print("""Min Heap - After decrease key of node [B -> -17]""")
my_min_heap.decrease_key(b, -17)

# After
for i in my_min_heap.heap:
						print(i)

if __name__ == "__main__":
						import doctest

						doctest.testmod()






