#!/bin/python3
import random
import gmpy2

def gcd(a, b):
	a, b = (max(a, b), min(a, b))

	while b != 0:
		a, b = (b, a % b)

	return a

PRODUCT_PRIMES_UNDER_100 = 2305567963945518424753102147331756070

# The following is an implementation of the Miller-Rabin primality test
def miller_rabin(n: int) -> int:
	# Repeat the test 40 times, thus the maximum error rate is 4^(-40) (basically negligible)
	for _ in range(40):
		a = random.randint(2, n - 2)

		exponent = n - 1

		while True:

			# If "exponent" is odd, we've reached the end of the factorization, so we may now check the last two factors for proper divisibility.  If they work, "n" passed the test for "a".  If they don't, we can be 100% positive that "n" is composite).
			if exponent & 1:
				if gmpy2.powmod(a, exponent, n) == 1 or gmpy2.powmod(a, exponent, n) == n - 1:
					break
				else:
					return False
			elif gmpy2.powmod(a, exponent, n) == n - 1:
				break

			# This simply divides the exponent by 2
			exponent >>= 1

	return True

def is_prime(n: int) -> int:
	# Basic test to eliminate trivial numbers and numbers that are easily not prime
	if 1 < n and n < 4:
		return True
	elif not n & 1 or n == 1 or (gcd(PRODUCT_PRIMES_UNDER_100, n) != 1 and n > 97):
		return False

	# At this point, use the Miller-Rabin test
	return miller_rabin(n)


# TESTING

# Takes roughly 14 seconds (including the print function calls, which are incredibly slow, only takes 11 seconds without the print calls)
for n in range(1000000):
	is_prime(n)

# Takes roughly 2 seconds with gmpy2.powmod (extremely optimized modular exponentiation that is written in native C code and is better than the native Python pow implementation)
#print(miller_rabin(941042957935892235278118405729346527936064852043509757786165859071524001380235444297640191288020772901104772823174069522008004366028519807290045552843360601623655065658769537578396274567517770311140904673330896578333393004607853725992709645428707511516550789208584637651522557064061937516680073379744929752567549370383885105859411669363045162083268412634084011282098415461921946683812699243048058551242483039327893874787894797678249015032104372162726055049951998752328803554020538534372336763614060313073253083764137555388084530705053497312975835779287166474973565895831501420436843339424689295467632601407205278124164776929287526466407878848130136679891927314936578370571377781962850617946109754811648997169703781855075054407854087234032914976600836472849814878901873101893512382494780857153941275500614714150023004567672460605559617457326755238414730821483256571472939067144010183919209530419611674511407829083972842447404562950557064564415470779096660287427475474905192371481424593215760208295109012411224447099478367960314419415841315315092730814380711517444955254593511923512969094314467836597157789592347220951385766897646982817061400361910151175749085648502257209694939263240920938369554151981910990123983352348517635661220247))