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:
  OUTPUT YES

Question

Since the decision problem is in $P$ must finding a solution also be solvable in polynomial-time?