So testing that condition for several random values of a can be used as evidence that p is probably prime.
This site explains the Fermat primality test and its flaws in more detail:
Run the file with this command:
from random import randint p = int(input("Input potential prime: ")) for i in range(5): a = randint(2,p-2) if pow(a, p-1, p) == 1: print("PASS for ", a, end="; ") else: print("FAIL for ", a, end="; ") print()
As shown below, 11 and 13 pass all the tests because they are prime, but 100 and 121 fail because they aren't.
It works, because Python really can handle any size of integer, as shown below.
C 503.1: Find the Next Prime (10 pts)This number is not prime:
Find the first number above it which is prime.
The flag is that number as one long integer, like
C 503.2: Companion Primes (10 pts extra)11 and 13 are both primes, only differing by two. Such primes are called companion primes.
Find the first set of companion primes above
The flag is the lower of the two primes, as one long integer, like