

'''simple docstring'''


import random







def 						SCREAMING_SNAKE_CASE(  UpperCamelCase  )    ->    bool:
	UpperCAmelCase_		:      List[str]       	=					num - 1
	UpperCAmelCase_		:      Tuple       	=					0

	while s % 2 == 0:
		UpperCAmelCase_		:      Optional[Any]       	=					s // 2
		t += 1

	for _ in range(5  ):
		UpperCAmelCase_		:      Dict       	=					random.randrange(2   ,num - 1  )
		UpperCAmelCase_		:      List[str]       	=					pow(UpperCamelCase   ,UpperCamelCase   ,UpperCamelCase  )
		if v != 1:
			UpperCAmelCase_		:      int       	=					0
			while v != (num - 1):
				if i == t - 1:
					return False
				else:
					UpperCAmelCase_		:      List[Any]       	=					i + 1
					UpperCAmelCase_		:      Optional[Any]       	=					(v**2) % num
	return True







def 						SCREAMING_SNAKE_CASE(  UpperCamelCase  )    ->    bool:
	if num < 2:
		return False

	UpperCAmelCase_		:      Dict       	=					[
	    2,
	    3,
	    5,
	    7,
	    1_1,
	    1_3,
	    1_7,
	    1_9,
	    2_3,
	    2_9,
	    3_1,
	    3_7,
	    4_1,
	    4_3,
	    4_7,
	    5_3,
	    5_9,
	    6_1,
	    6_7,
	    7_1,
	    7_3,
	    7_9,
	    8_3,
	    8_9,
	    9_7,
	    1_0_1,
	    1_0_3,
	    1_0_7,
	    1_0_9,
	    1_1_3,
	    1_2_7,
	    1_3_1,
	    1_3_7,
	    1_3_9,
	    1_4_9,
	    1_5_1,
	    1_5_7,
	    1_6_3,
	    1_6_7,
	    1_7_3,
	    1_7_9,
	    1_8_1,
	    1_9_1,
	    1_9_3,
	    1_9_7,
	    1_9_9,
	    2_1_1,
	    2_2_3,
	    2_2_7,
	    2_2_9,
	    2_3_3,
	    2_3_9,
	    2_4_1,
	    2_5_1,
	    2_5_7,
	    2_6_3,
	    2_6_9,
	    2_7_1,
	    2_7_7,
	    2_8_1,
	    2_8_3,
	    2_9_3,
	    3_0_7,
	    3_1_1,
	    3_1_3,
	    3_1_7,
	    3_3_1,
	    3_3_7,
	    3_4_7,
	    3_4_9,
	    3_5_3,
	    3_5_9,
	    3_6_7,
	    3_7_3,
	    3_7_9,
	    3_8_3,
	    3_8_9,
	    3_9_7,
	    4_0_1,
	    4_0_9,
	    4_1_9,
	    4_2_1,
	    4_3_1,
	    4_3_3,
	    4_3_9,
	    4_4_3,
	    4_4_9,
	    4_5_7,
	    4_6_1,
	    4_6_3,
	    4_6_7,
	    4_7_9,
	    4_8_7,
	    4_9_1,
	    4_9_9,
	    5_0_3,
	    5_0_9,
	    5_2_1,
	    5_2_3,
	    5_4_1,
	    5_4_7,
	    5_5_7,
	    5_6_3,
	    5_6_9,
	    5_7_1,
	    5_7_7,
	    5_8_7,
	    5_9_3,
	    5_9_9,
	    6_0_1,
	    6_0_7,
	    6_1_3,
	    6_1_7,
	    6_1_9,
	    6_3_1,
	    6_4_1,
	    6_4_3,
	    6_4_7,
	    6_5_3,
	    6_5_9,
	    6_6_1,
	    6_7_3,
	    6_7_7,
	    6_8_3,
	    6_9_1,
	    7_0_1,
	    7_0_9,
	    7_1_9,
	    7_2_7,
	    7_3_3,
	    7_3_9,
	    7_4_3,
	    7_5_1,
	    7_5_7,
	    7_6_1,
	    7_6_9,
	    7_7_3,
	    7_8_7,
	    7_9_7,
	    8_0_9,
	    8_1_1,
	    8_2_1,
	    8_2_3,
	    8_2_7,
	    8_2_9,
	    8_3_9,
	    8_5_3,
	    8_5_7,
	    8_5_9,
	    8_6_3,
	    8_7_7,
	    8_8_1,
	    8_8_3,
	    8_8_7,
	    9_0_7,
	    9_1_1,
	    9_1_9,
	    9_2_9,
	    9_3_7,
	    9_4_1,
	    9_4_7,
	    9_5_3,
	    9_6_7,
	    9_7_1,
	    9_7_7,
	    9_8_3,
	    9_9_1,
	    9_9_7,
	]

	if num in low_primes:
		return True

	for prime in low_primes:
		if (num % prime) == 0:
			return False

	return rabin_miller(UpperCamelCase  )







def 						SCREAMING_SNAKE_CASE(  UpperCamelCase = 1_0_2_4  )    ->    int:
	while True:
		UpperCAmelCase_		:      Union[str, Any]       	=					random.randrange(2 ** (keysize - 1)   ,2 ** (keysize)  )
		if is_prime_low_num(UpperCamelCase  ):
			return num


if __name__ == "__main__":
						lowerCAmelCase__										= generate_large_prime()
						print(("Prime number:", num))
						print(("is_prime_low_num:", is_prime_low_num(num)))









'''simple docstring'''


class 					lowercase						:


							def __init__(			self)							->				Dict:
								UpperCAmelCase_		:      List[str]       	=					0
								UpperCAmelCase_		:      str       	=					0
								UpperCAmelCase_		:      Union[str, Any]       	=					{}


							def 						_snake_case							(			self    ,			_snake_case)							->				Tuple:
								if vertex not in self.adjacency:
									UpperCAmelCase_		:      Tuple       	=					{}
									self.num_vertices += 1


							def 						_snake_case							(			self    ,			_snake_case    ,			_snake_case    ,			_snake_case)							->				Any:
								self.add_vertex(_snake_case)
								self.add_vertex(_snake_case)

								if head == tail:
									return

								UpperCAmelCase_		:      str       	=					weight
								UpperCAmelCase_		:      Optional[int]       	=					weight


							def 						_snake_case							(			self)							->				Union[str, Any]:
								UpperCAmelCase_		:      Dict       	=					self.get_edges()
								for edge in edges:
									UpperCAmelCase_	,    UpperCAmelCase_	,    UpperCAmelCase_		:      str       	=					edge
									edges.remove((tail, head, weight))
								for i in range(len(_snake_case)):
									UpperCAmelCase_		:      Union[str, Any]       	=					list(edges[i])

								edges.sort(key=lambda _snake_case: e[2])
								for i in range(len(_snake_case) - 1):
									if edges[i][2] >= edges[i + 1][2]:
										UpperCAmelCase_		:      Tuple       	=					edges[i][2] + 1
								for edge in edges:
									UpperCAmelCase_	,    UpperCAmelCase_	,    UpperCAmelCase_		:      List[Any]       	=					edge
									UpperCAmelCase_		:      Any       	=					weight
									UpperCAmelCase_		:      Union[str, Any]       	=					weight


							def __str__(			self)							->				str:
								UpperCAmelCase_		:      int       	=					''
								for tail in self.adjacency:
									for head in self.adjacency[tail]:
										UpperCAmelCase_		:      Dict       	=					self.adjacency[head][tail]
										string += F"""{head} -> {tail} == {weight}\n"""
								return string.rstrip('\n')


							def 						_snake_case							(			self)							->				str:
								UpperCAmelCase_		:      Optional[int]       	=					[]
								for tail in self.adjacency:
									for head in self.adjacency[tail]:
										output.append((tail, head, self.adjacency[head][tail]))
								return output


							def 						_snake_case							(			self)							->				Any:
								return self.adjacency.keys()


							@staticmethod
							def 						_snake_case							(			_snake_case=None    ,			_snake_case=None)							->				Dict:
								UpperCAmelCase_		:      List[str]       	=					Graph()
								if vertices is None:
									UpperCAmelCase_		:      Optional[Any]       	=					[]
								if edges is None:
									UpperCAmelCase_		:      int       	=					[]
								for vertex in vertices:
									g.add_vertex(_snake_case)
								for edge in edges:
									g.add_edge(*_snake_case)
								return g



							class 					lowercase						:


														def __init__(			self)							->				Dict:
															UpperCAmelCase_		:      Tuple       	=					{}
															UpperCAmelCase_		:      str       	=					{}


														def __len__(			self)							->				List[Any]:
															return len(self.parent)


														def 						_snake_case							(			self    ,			_snake_case)							->				Union[str, Any]:
															if item in self.parent:
																return self.find(_snake_case)

															UpperCAmelCase_		:      Any       	=					item
															UpperCAmelCase_		:      List[str]       	=					0
															return item


														def 						_snake_case							(			self    ,			_snake_case)							->				str:
															if item not in self.parent:
																return self.make_set(_snake_case)
															if item != self.parent[item]:
																UpperCAmelCase_		:      Dict       	=					self.find(self.parent[item])
															return self.parent[item]





														def 						_snake_case							(			self    ,			_snake_case    ,			_snake_case)							->				int:
															UpperCAmelCase_		:      List[str]       	=					self.find(_snake_case)
															UpperCAmelCase_		:      List[str]       	=					self.find(_snake_case)

															if roota == roota:
																return roota

															if self.rank[roota] > self.rank[roota]:
																UpperCAmelCase_		:      int       	=					roota
																return roota

															if self.rank[roota] < self.rank[roota]:
																UpperCAmelCase_		:      Dict       	=					roota
																return roota

															if self.rank[roota] == self.rank[roota]:
																self.rank[roota] += 1
																UpperCAmelCase_		:      Any       	=					roota
																return roota
															return None


							@staticmethod
							def 						_snake_case							(			_snake_case)							->				int:
								UpperCAmelCase_		:      Optional[Any]       	=					graph.num_vertices

								UpperCAmelCase_		:      Optional[int]       	=					Graph.UnionFind()
								UpperCAmelCase_		:      int       	=					[]
								while num_components > 1:
									UpperCAmelCase_		:      Any       	=					{}
									for vertex in graph.get_vertices():
										UpperCAmelCase_		:      Optional[Any]       	=					-1

									UpperCAmelCase_		:      List[str]       	=					graph.get_edges()
									for edge in edges:
										UpperCAmelCase_	,    UpperCAmelCase_	,    UpperCAmelCase_		:      List[str]       	=					edge
										edges.remove((tail, head, weight))
									for edge in edges:
										UpperCAmelCase_	,    UpperCAmelCase_	,    UpperCAmelCase_		:      Union[str, Any]       	=					edge
										UpperCAmelCase_		:      Any       	=					union_find.find(_snake_case)
										UpperCAmelCase_		:      Dict       	=					union_find.find(_snake_case)
										if seta != seta:
											if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
												UpperCAmelCase_		:      List[str]       	=					[head, tail, weight]

											if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
												UpperCAmelCase_		:      str       	=					[head, tail, weight]
									for vertex in cheap_edge:
										if cheap_edge[vertex] != -1:
											UpperCAmelCase_	,    UpperCAmelCase_	,    UpperCAmelCase_		:      Any       	=					cheap_edge[vertex]
											if union_find.find(_snake_case) != union_find.find(_snake_case):
												union_find.union(_snake_case    ,			_snake_case)
												mst_edges.append(cheap_edge[vertex])
												UpperCAmelCase_		:      Tuple       	=					num_components - 1
								UpperCAmelCase_		:      int       	=					Graph.build(edges=_snake_case)
								return mst






