Function Problem that finds the solution
Given integer for N.
Find 2 integers distinct from N. (But, less than N)
That have a product equal to N.
This means we must exclude integers 1 and N.
An algorithm that is pseudo-polynomial
N = 10
numbers = []
for a in range(2, N):
numbers.append(a)
for j in range(length(numbers)):
if N/(numbers[j]) in numbers:
OUTPUT N/(numbers[j]) X numbers[j]
break
Output
Soltuion Verified: 5 x 2 = N and N=10
The algorithm that solves the Decision Problem
if AKS-primality(N) == False:
if N != 1:
OUTPUT YES
Question
Since the decision problem is in P must finding a solution also be solvable in polynomial-time?