from math import sqrt
def isPrime(n):
	if (n < 2):
		return False
	elif (n == 2 or n == 3):
		return True
	else:
		for i in range(2,int(sqrt(n))+1):
			if (n % i == 0):
				return False
		return True

def getFactors(n):
	f = []
	for i in range(1,n+1):
		if (n % i == 0):
			f.append(i)
	return f

def closestFactor(f,c):
	diff = pow(c,3)
	for i in range(0,len(f)):
		if (abs(f[i] - c) < diff):
			diff = abs(f[i] - c)
			a = f[i]
	return a
	
def roxanneMethod(num_candies):
	factors = getFactors(num_candies)
	cuberoot = pow(num_candies,1./3)
	if (pow(int(cuberoot),3) == num_candies):
		a = int(cuberoot)
		b = a
		c = a
	else:
		a = closestFactor(factors,cuberoot)	
		if (isPrime(int(num_candies/a))):
			b = 1
			c = num_candies / a
		else:
			squareroot = pow(num_candies/a,1./2)
			if (pow(int(squareroot),2) == int(num_candies/a)):
				b = int(squareroot)
				c = b
			else:
				factors = getFactors(num_candies/a)
				#print(num_candies /a )
				#print(factors
				b = closestFactor(factors,squareroot)
				c = int((num_candies/a)/b)
		squareroot = pow(a * b, 1./2)
		factors = getFactors(a * b)
		a_star = closestFactor(factors,squareroot)
		b_star = (a*b)/a_star
		if (abs(a_star-b_star) < abs(a-b)):
			a = a_star
			b = b_star
	
		squareroot = pow(a * c, 1./2)
		factors = getFactors(a * c)
		a_star = closestFactor(factors,squareroot)
		c_star = (a*c)/a_star
		if (abs(a_star-c_star) < abs(a-c)):
			a = a_star
			c = c_star
	l = [a,b,c]
	return l

# num_c = int(input("How many candies do you want to package: "))
# while (num_c < 1):
# 	num_c = int(input("How many candies do you want to package: "))
# 
# ans = roxanneMethod(num_c)
# print(ans)

u = int(input("Do you want to get a list of answers? Type 1. Do you want to manually try numbers? Type 2."))
if (u == 1):
	max = int(input("What number do you want to print up to?"))
	for i in range(1,max + 1):
		print("num candies = " + str(i) + " and Roxanne method gives " + str(roxanneMethod(i)))
else:
	while True:
		choice = int(input("What number would you like to check? "))
		print("The roxanne method returns: " + str(roxanneMethod(choice)))