# Algorithm always provide a $2$_$sum$ with at least ONE prime? In polynomial-time?

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$$.

## Algorithm

$$N$$ = $$13$$

$$s$$ = $$binary~length~of~N$$

$$p$$ = 0

$$count$$ = $$0$$

$$primes$$ = []

$$WHILE$$ $$count$$ $$<$$ $$s$$:

$$~~~~~~~~~$$ $$p$$=$$p$$+$$1$$

$$~~~~~~~~~$$ $$IF$$ $$AKS$$-$$PRIMALITY$$($$p$$) == $$TRUE$$:

$$~~~~~~~~~~~~~~~~~~~$$ $$primes$$.append($$p$$)

$$~~~~~~~~~~~~~~~~~~~$$ $$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.

## Question

What would be the best estimate of the time complexity?

Would it fail if $$P$$ $$>$$ $$N$$? (an easy fix)

• I can improve space complexity by getting rid of the appending and just using $primes$ = $p$ instead! I noticed a speedup in python by doing this! – Dingle Berry May 27 '20 at 2:09
• What does the output have to do with $N$? What is a 2_Sum? What's wrong with $P=2$? – Yonatan N May 27 '20 at 6:32
• @YonatanN That would be boring if we use fixed primes. And, I should've said that that a 2_sum is two integers added together that equals $N$. – Dingle Berry May 28 '20 at 0:35