# *************************************************************************
# Prime nubers test
#
# Author: ing. Robert Polak
# Contact Info: robopol@robopol.sk
# website: https://www.robopol.sk
# Purpose:
#           An efficient algorithm for determining large primes.
#
# 'type: console program' 
# Copyright notice: This code is Open Source and should remain so.
# *************************************************************************
import sys

print("***********************************************************************************")
print("Prime number test:")
print("")
print("This program improved finding of prime numbers using a small Fermat theorem.")
print("If it gets the statement: prime or pseudoprime, then it is a probability")
print("result, with pseudoprimes having a low probability.")
print("Pseudoprimes are false primes. For a better result changes the basis a = 3,4,5,7...")
print("")
print("To end the program, press 0 and the enter.")
print("***********************************************************************************")

# defining the necessary constants.
b_first=int(251)
basic_field=[2,3,5,7]
# The basis of the power of Fermat's theorem.
a=int(2)
# Function for entering an numbers
def get_input():
    while True:
        try:
            print("Enter the number:")
            input_string=sys.stdin.readline()
            number_int=int(input_string)
        except Exception:
            print("Please insert only integer values")
            continue
        break
    return number_int

# Infinite while loop.
while True:
    n=number=get_input()
    stop=False
    
    # end of program    
    if number == 0:
        break
    # filtering to basic conditions
    for divisor in basic_field:
        if number % divisor == 0:
            print("Number is composite, the first divisor is:",divisor)
            stop=True
            break
                      
    # filtering by an improved algorithm of a reduced, small Fermat theorem, create: robopol.sk.
    if stop == False:
            print("wait")
            # defining the necessary constants.
            cycle_end=cycle= int(a**b_first % n)
            complet_end=complet=b_first
            fermat=n - 1
            k=fermat
            # We define an array of residues, numbers.
            field_num=[b_first]
            field_res=[cycle]
            # We will fill these fields.
            while complet < fermat:
                if 2*complet >= fermat:
                    break
                cycle=cycle**2
                if cycle > n:
                    cycle=cycle % n
                    if cycle == 0: cycle=n
                complet=2*complet
                field_num=field_num + [complet]
                field_res=field_res + [cycle]
            
            # Main algorithm.                       
            while k > b_first:
                index=0
                for num in field_num:
                    if num < k: 
                        maximum = num
                        max_cycle = field_res [index]
                    index +=1
                complet_end += maximum
                cycle_end = cycle_end*max_cycle
                if cycle_end > n:
                    cycle_end=cycle_end % n
                    if cycle_end == 0: cycle_end=n
                k= fermat - complet_end                

            # determination of conditions for prime numbers.
            remainder = int((cycle_end * a ** k) % n)
            print ("Remainder is:", remainder)
            # Robopol test, if remainder is n-1 for (n-1)/2 and remainder is 1 for n-1, number is prime.
            print("Robopol test, if remainder is n-1 for (n-1)/2 and remainder is 1 for n-1, number is 100% prime.")
            if remainder == 1 or remainder == n-1:
                print("Number is prime or pseudoprime, pseudoprimes are very unlikely.")                           
            if remainder > 1 and remainder < (n - 1):
                print("Number is composite.")