# Seth Jones
# 10/28/2026
# Code for CIS 3362 Homework #5 Problem 6

import math


#Determine if a number is prime or not
def isPrime(p):
    if p == 2: return True
    for i in range(2,math.ceil(math.sqrt(p)) + 1):
        if p%i == 0:
            return False
        if i == math.ceil(math.sqrt(p)):
            return True

#Returns three primes within our desired range
def ThreePrimes():
    import random
    primes = []

    while(len(primes) < 3):
        rand = random.randint(20,50)
        if rand in primes: continue
        if isPrime(rand):
            primes.append(rand)
    return primes


#Returns prime factors, brute force
def primeFactors(p):
    primes = {}

    for i in range(p//2 + 1):
        if isPrime(i):
            while(p%i == 0):
                primes[i] = primes.get(i, 0) + 1
                p //= i
    return primes


#Calculates Phi of a number
def phi(p):

    if(isPrime(p)): return p - 1
    sum = 1
    primes = primeFactors(p)
    for prime, i in primes.items():
        sum *= pow(prime,i) - pow(prime,i - 1)
    return sum




threePrimes = ThreePrimes()


#Create list of list for our generators
allGenerators = []

for prime in threePrimes:
    #list of gen
    generators = []
    for i in range(2,prime):
        map = {}
        flag = False
        for j in range(prime-1):
            check = pow(i,j)%prime
            if check in map:
                continue

            map[check] = 1

            if j == prime - 2:
                generators.append(i)
    allGenerators.append(generators)

for i,generators in enumerate(allGenerators):
    print(f"{threePrimes[i]} Prime")
    print(f"{generators} Generators")
    print(f"{len(generators)} length of generators")
    print(f"{phi(threePrimes[i] - 1)} phi(p-1)")
