nontrivial-roots.py

#!/usr/bin/python

def roots(n):
    for a in range(0, n):
        if (a*a) % n == 1:
            yield a

def prime(n):
    for a in range(2, n):
        if n % a == 0:
            return False
    return True

def composite(n): return not prime(n)

def factors(n):
    a = 3
    while n != 1:
        if n % a == 0:
            yield a
            n /= a
        else:
            a += 2

print("{0:<7} {1:<14} {2:<40} {3}".format("N", "Factors", "Roots", "Conjecture"))

for n in range(3, 20, 2):
    if composite(n):
        f = list(set(factors(n)))
        r = list(roots(n))
        c = 2**len(f) == len(r)

        print("{0:<7} {1:<14} {2:<40} {3}".format(n, f, r, c))