Chef has been exploring prime numbers lately, and has recently made a conjecture resembling
one of Goldbach's conjectures.
Chef's conjecture is that any odd number greater than 61 can be expressed as the sum of
a prime, a square of a prime, and a cube of a prime.
He wants you to help verify his conjecture for small numbers.
Note: negative numbers are never considered to be prime, nor are 0 and 1.

------ Input ------ 

Input will consist of a series of odd numbers greater than 61 and less than 10^{6}, 
one per line, terminated by the number 0 on a line by itself.
There will be at most 1000 lines.

------ Output ------ 

For each odd number in the input, print 3 primes P_{1}, P_{2}, P_{3} on a line,
where P_{1} + P_{2}^{2} + P_{3}^{3} is equal to the number from the input.
If no such primes exist, print "0 0 0" instead (quotes for clarity).
If there are multiple triplets of primes that satisfy the equation, print any such triplet.

----- Sample Input 1 ------ 
81
85
155
0
----- Sample Output 1 ------ 
5 7 3
73 2 2
5 5 5

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Complete search

Number theory

Mathematics

Ad-hoc


Solutions:
def sieve_erasth(num):
	primes = [True] * num
	primes[0] = False
	primes[1] = False
	p = 2
	while p * p <= num:
		if primes[p] == True:
			for i in range(p * p, num, p):
				primes[i] = False
		p += 1
	return primes
num = 10 ** 6
primes = sieve_erasth(num)

def solve(n):
	for a in range(100, 1, -1):
		if primes[a] == False:
			continue
		for b in range(1000, 1, -1):
			if primes[b] == False:
				continue
			c = n - (a ** 3 + b ** 2)
			if c > 0 and primes[c]:
				return [c, b, a]
	return [0, 0, 0]
while True:
	n = int(input())
	if n == 0:
		break
	print(*solve(n))


mod = 1000000007
read_int = lambda : int(input().strip())
read_str = lambda : input().strip()
read_str_arr = lambda : input().strip().split()
read_int_arr = lambda : [int(x) for x in input().strip().split()]
isprime = [False] * 2 + [True] * (10 ** 6 - 2)
for i in range(2, len(isprime)):
	if not isprime[i]:
		continue
	for j in range(i * i, len(isprime), i):
		isprime[j] = False
from math import floor, sqrt

def solve(n):
	for p3 in range(floor((n - 6) ** (1 / 3)), 1, -1):
		if not isprime[p3]:
			continue
		for p2 in range(floor(sqrt(n - p3 ** 3 - 2)), 1, -1):
			if not isprime[p2]:
				continue
			if isprime[n - p3 ** 3 - p2 ** 2]:
				print(n - p3 ** 3 - p2 ** 2, p2, p3)
				return
	print('0 0 0')
while True:
	n = read_int()
	if n == 0:
		break
	solve(n)


ul = 10 ** 6
prime = [1] * (ul + 1)
prime[0] = 0
prime[1] = 0
i = 2
while i * i <= ul:
	if prime[i] == 1:
		for j in range(i * i, ul + 1, i):
			prime[j] = 0
	i += 1

def solve(n):
	for pc in range(100, 1, -1):
		if prime[pc] == 0:
			continue
		for ps in range(1000, 1, -1):
			if prime[ps] == 0:
				continue
			el = n - (ps ** 2 + pc ** 3)
			if el > 0 and prime[el] == 1:
				return [el, ps, pc]
	return [0, 0, 0]
while True:
	n = int(input())
	if n == 0:
		break
	print(*solve(n))


import bisect
import math
n = 10 ** 6 + 1
prime = [True for i in range(n)]
prime[0] = prime[1] = False
p = 2
arr_square = []
square = []
squareset = set()
arr_cube = []
while p * p <= n:
	if prime[p] == True:
		for i in range(p * 2, n, p):
			prime[i] = False
	p += 1
for i in range(n):
	if prime[i]:
		arr_cube.append(pow(i, 3))
		arr_square.append(pow(i, 2))
		square.append(i)
		squareset.add(i)
while True:
	x = int(input())
	if x == 0:
		break
	else:
		num = int(x ** (1 / 3))
		cube_index = bisect.bisect_right(square, num)
		num = int(x ** 0.5)
		square_index = bisect.bisect_right(square, num)
		fla = True
		for i in range(cube_index, -1, -1):
			for j in range(square_index, -1, -1):
				if x - (arr_cube[i] + arr_square[j]) in squareset and x - (arr_cube[i] + arr_square[j]) + arr_cube[i] + arr_square[j] == x:
					print(x - (arr_square[j] + arr_cube[i]), square[j], square[i])
					fla = False
					break
			if not fla:
				break
		if fla:
			print(0, 0, 0)


def main():
	prime = [True for i in range(1000001)]
	p = 2
	prm = []
	while p * p <= 1000001:
		if prime[p] == True:
			prm.append(p)
			for i in range(p * 2, 10 ** 6 + 1, p):
				prime[i] = False
		p += 1
	c = 1
	pp = prm[::-1]
	prime[0] = prime[1] = False
	while c:
		n = int(input())
		if n == 0:
			c = 0
			continue
		cbrt = int(n ** (1 / 3))
		sqrt = int(n ** (1 / 2))
		flag = 1
		for i in pp:
			if flag:
				for j in pp:
					if i <= cbrt + 1 and j <= sqrt + 1 and (n - i ** 3 - j ** 2 > 0) and prime[n - i ** 3 - j ** 2]:
						print(n - i ** 3 - j ** 2, j, i)
						flag = 0
						break
			else:
				break
		if flag:
			print(0, 0, 0)
main()