To optimize this you have to invest your mathematical knowledge.
You should start from calculating prime using Sieve of Eratosthenes or some better algorithm.
Then note that all your q
but first must be odd. All primes except 2
are odd and all their multiplication is odd too. As a result only first item in q
is even.
Why this is important? Your sum has even number of elements, so to be able to have odd outcome which could match E
in q
, A
must be equal to first element of q
since it only even value in q
.
So you have only 3 free parameters: B
, C
and D
and E
can be calculated and check if it exists.
You can iterate over B
, C
, D
and then binary search for E
in q
. This will gives algorithm with complexity O(n^3 log n)
which is great comparing to your O(n^5)
.
You can use unordered_set
to match E
in O(1)
time instead of O(log n)
time. So final algorithm easily ca be O(n^3)
.
I’m quite sure you can find this kind tricks more effectively. Possibly knowledge of d
value could be used in some way to avoid some iterations.
CLICK HERE to find out more related problems solutions.