



"""simple docstring"""
from __future__ import annotations

import matplotlib.pyplot as plt  # type: ignore
import numpy

# initial triangle of Koch snowflake
SCREAMING_SNAKE_CASE_				= numpy.array([0, 0])
SCREAMING_SNAKE_CASE_				= numpy.array([0.5, 0.8660254])
SCREAMING_SNAKE_CASE_				= numpy.array([1, 0])
SCREAMING_SNAKE_CASE_				= [VECTOR_1, VECTOR_2, VECTOR_3, VECTOR_1]



def        lowerCAmelCase_						(							SCREAMING_SNAKE_CASE__, SCREAMING_SNAKE_CASE__	)			->      list[numpy.ndarray]:
		a_     :      Union[str, Any] 						=     initial_vectors
		for _ in range(SCREAMING_SNAKE_CASE__	):
				a_     :      int 						=     iteration_step(SCREAMING_SNAKE_CASE__	)
		return vectors



def        lowerCAmelCase_						(							SCREAMING_SNAKE_CASE__	)			->      list[numpy.ndarray]:
		a_     :      Dict 						=     []
		for i, start_vector in enumerate(vectors[:-1]	):
				a_     :      int 						=     vectors[i + 1]
				new_vectors.append(SCREAMING_SNAKE_CASE__	)
				a_     :      int 						=     end_vector - start_vector
				new_vectors.append(start_vector + difference_vector / 3	)
				new_vectors.append(
				    start_vector + difference_vector / 3 + rotate(difference_vector / 3, 60	)	)
				new_vectors.append(start_vector + difference_vector * 2 / 3	)
		new_vectors.append(vectors[-1]	)
		return new_vectors



def        lowerCAmelCase_						(							SCREAMING_SNAKE_CASE__, SCREAMING_SNAKE_CASE__	)			->      numpy.ndarray:
		a_     :      str 						=     numpy.radians(SCREAMING_SNAKE_CASE__	)
		a_     :      List[str] 						=     numpy.cos(SCREAMING_SNAKE_CASE__	), numpy.sin(SCREAMING_SNAKE_CASE__	)
		a_     :      Any 						=     numpy.array(((c, -s), (s, c))	)
		return numpy.dot(SCREAMING_SNAKE_CASE__, SCREAMING_SNAKE_CASE__	)



def        lowerCAmelCase_						(							SCREAMING_SNAKE_CASE__	)			->      None:
		a_     :      Optional[Any] 						=     plt.gca()
		axes.set_aspect("equal"	)

		# matplotlib.pyplot.plot takes a list of all x-coordinates and a list of all
		# y-coordinates as inputs, which are constructed from the vector-list using
		# zip()
		a_     :      List[Any] 						=     zip(*SCREAMING_SNAKE_CASE__	)
		plt.plot(SCREAMING_SNAKE_CASE__, SCREAMING_SNAKE_CASE__	)
		plt.show()


if __name__ == "__main__":
					import doctest

					doctest.testmod()

					SCREAMING_SNAKE_CASE_				= iterate(INITIAL_VECTORS, 5)
					plot(processed_vectors)




"""simple docstring"""
def        lowerCAmelCase_						(							SCREAMING_SNAKE_CASE__, SCREAMING_SNAKE_CASE__ = False	)			->      bool:
		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
		a_     :      Optional[Any] 						=     [
		    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,
		]

		a_     :      Optional[int] 						=     [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
		for idx, _p in enumerate(SCREAMING_SNAKE_CASE__, 1	):
				if n < _p:
						# then we have our last prime to check
						a_     :      List[Any] 						=     primes[:idx]
						break
		a_						,				a_     :      Tuple 						=     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:
				a_     :      str 						=     False
				for r in range(SCREAMING_SNAKE_CASE__	):
						a_     :      List[str] 						=     pow(SCREAMING_SNAKE_CASE__, d * 2**r, SCREAMING_SNAKE_CASE__	)
						# see article for analysis explanation for m
						if (r == 0 and m == 1) or ((m + 1) % n == 0):
								a_     :      List[Any] 						=     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        lowerCAmelCase_						(							)			->      None:
		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()