Function Problem: Given $N$ find a $2$_$sum$ that uses at least $ONE$ prime.
Fact: Prime Gaps grow logarithmically on average. And, in worst case if memory serves correct it grows with a bounded constant.
- Take notice that $count$ (defined below) will only equal to $s$, if the $AKS$ primality statement executes $s$ times. This will find our $s$-amount primes to generate a $2$_$sum$ by finding the difference of $N$-$P$.
$N$ = $13$
$s$ = $binary~length~of~N$
$p$ = 0
$count$ = $0$
$primes$ = 
$WHILE$ $count$ $<$ $s$:
$~~~~~~~~~$ $IF$ $AKS$-$PRIMALITY$($p$) == $TRUE$:
$~~~~~~~~~~~~~~~~~~~$ $count$ = $count$ + 1
$OUTPUT$ FOUND $2$_$SUM$, $(N-P)$ + $P$
$OUTPUT$ VERIFY SOLUTION $(N-P)$+$P$ == $N$
Found 2-sum: 6 + 7 Verify Solution: True
I'm an amateur who made computer-science a hobby, and I'm not sure what would the exact time complexity would be.
What would be the best estimate of the time complexity?
Would it fail if $P$ $>$ $N$? (an easy fix)