



'''simple docstring'''



def   _A       (   _lowerCAmelCase  ,   _lowerCAmelCase = False					):



							"""simple docstring"""



							if n == 2:
														return True
							if not n % 2 or n < 2:
														return False
							if n > 5 and n % 10 not in (1, 3, 7, 9):  # can quickly check last digit
														return False
							if n > 3_317_044_064_679_887_385_961_981 and not allow_probable:
														raise ValueError(
														    'Warning: upper bound of deterministic test is exceeded. '
														    'Pass allow_probable=True to allow probabilistic test. '
														    'A return value of True indicates a probable prime.'					)
							# array bounds provided by analysis
							__lowercase       	=[
							    2_047,
							    1_373_653,
							    25_326_001,
							    3_215_031_751,
							    2_152_302_898_747,
							    3_474_749_660_383,
							    341_550_071_728_321,
							    1,
							    3_825_123_056_546_413_051,
							    1,
							    1,
							    318_665_857_834_031_151_167_461,
							    3_317_044_064_679_887_385_961_981,
							]

							__lowercase       	=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
							for idx, _p in enumerate(_lowerCAmelCase  ,   1					):
														if n < _p:
																					# then we have our last prime to check
																					__lowercase       	=primes[:idx]
																					break
							__lowercase	,				__lowercase       	=n - 1, 0
							# break up n -1 into a power of 2 (s) and
							# remaining odd component
							# essentially, solve for d * 2 ** s == n - 1
							while d % 2 == 0:
														d //= 2
														s += 1
							for prime in plist:
														__lowercase       	=False
														for r in range(_lowerCAmelCase					):
																					__lowercase       	=pow(_lowerCAmelCase  ,   d * 2**r  ,   _lowerCAmelCase					)
																					# see article for analysis explanation for m
																					if (r == 0 and m == 1) or ((m + 1) % n == 0):
																												__lowercase       	=True
																												# this loop will not determine compositeness
																												break
														if pr:
																					continue
														# if pr is False, then the above loop never evaluated to true,
														# and the n MUST be composite
														return False
							return True



def   _A       (   ):



							"""simple docstring"""



							assert not miller_rabin(561					)
							assert miller_rabin(563					)
							# 2047

							assert not miller_rabin(838_201					)
							assert miller_rabin(838_207					)
							# 1_373_653

							assert not miller_rabin(17_316_001					)
							assert miller_rabin(17_316_017					)
							# 25_326_001

							assert not miller_rabin(3_078_386_641					)
							assert miller_rabin(3_078_386_653					)
							# 3_215_031_751

							assert not miller_rabin(1_713_045_574_801					)
							assert miller_rabin(1_713_045_574_819					)
							# 2_152_302_898_747

							assert not miller_rabin(2_779_799_728_307					)
							assert miller_rabin(2_779_799_728_327					)
							# 3_474_749_660_383

							assert not miller_rabin(113_850_023_909_441					)
							assert miller_rabin(113_850_023_909_527					)
							# 341_550_071_728_321

							assert not miller_rabin(1_275_041_018_848_804_351					)
							assert miller_rabin(1_275_041_018_848_804_391					)
							# 3_825_123_056_546_413_051

							assert not miller_rabin(79_666_464_458_507_787_791_867					)
							assert miller_rabin(79_666_464_458_507_787_791_951					)
							# 318_665_857_834_031_151_167_461

							assert not miller_rabin(552_840_677_446_647_897_660_333					)
							assert miller_rabin(552_840_677_446_647_897_660_359					)
							# 3_317_044_064_679_887_385_961_981
							# upper limit for probabilistic test


if __name__ == "__main__":
		test_miller_rabin()








'''simple docstring'''



from functools import lru_cache



def   _A       (   _lowerCAmelCase					):



							"""simple docstring"""



							__lowercase       	=2
							__lowercase       	=set()
							while i * i <= n:
														if n % i:
																					i += 1
														else:
																					n //= i
																					factors.add(_lowerCAmelCase					)
							if n > 1:
														factors.add(_lowerCAmelCase					)
							return factors



@lru_cache
def   _A       (   _lowerCAmelCase					):



							"""simple docstring"""



							return len(unique_prime_factors(_lowerCAmelCase					)					)



def   _A       (   _lowerCAmelCase					):



							"""simple docstring"""



							return len(set(_lowerCAmelCase					)					) in (0, 1)



def   _A       (   _lowerCAmelCase					):



							"""simple docstring"""



							__lowercase       	=2

							while True:
														# Increment each value of a generated range
														__lowercase       	=[base + i for i in range(_lowerCAmelCase					)]

														# Run elements through out unique_prime_factors function
														# Append our target number to the end.
														__lowercase       	=[upf_len(_lowerCAmelCase					) for x in group]
														checker.append(_lowerCAmelCase					)

														# If all numbers in the list are equal, return the group variable.
														if equality(_lowerCAmelCase					):
																					return group

														# Increment our base variable by 1
														base += 1



def   _A       (   _lowerCAmelCase = 4					):



							"""simple docstring"""



							__lowercase       	=run(_lowerCAmelCase					)
							return results[0] if len(_lowerCAmelCase					) else None


if __name__ == "__main__":
		print(solution())



