I have submited after that another one.

Thank you, the first solution is very nice! I didn't really get the second one at first, but now I think I got that one too. I think you wanted to write $$$l_i > (1-\frac{1}{1.4}) \cdot s$$$. Here's a description I wrote for myself to better understand the method:

So basically we have 3 intervals $$$A=[0s;(1-\frac{1}{1.4})s]$$$, $$$B=[(1-\frac{1}{1.4})s;\frac{1}{1.4}s]$$$ and $$$C=[\frac{1}{1.4}s;s]$$$. If for some $$$l_i \in C$$$ we're done. Continuing with the second interval, because $$$1-\frac{1}{1.4}>\frac{1}{4}$$$, a solution with $$$4$$$ elements from $$$B$$$ cannot be valid, but also because $$$3 \cdot (1-\frac{1}{1.4}) > \frac{1}{1.4}$$$ if there's a solution with $$$3$$$ elements from $$$B$$$ the smallest $$$3$$$ must also form a solution. Thus we have three cases left, we either choose $$$2$$$, $$$1$$$ or $$$0$$$ elements from $$$B$$$. Here goes a handy claim that helps in all $$$3$$$ cases: let the sum of all left ends that lie in interval $$$A$$$ be $$$X$$$, if we choose some different elements from $$$B$$$ such that their sum $$$Y$$$ is smaller than $$$\frac{1}{1.4}s$$$, but $$$Y+X \geq \frac{1}{1.4}s$$$ then there is a solution, since if $$$Y+X \leq 1$$$ there is obviously one, but in the case $$$Y+X>1$$$ we can take out elements from $$$A$$$ until the sum will be smaller or equal than $$$X+Y$$$ and since all the elements we take out are $$$\leq 1-\frac{1}{1.4}$$$ we can't take out an element and then have a sum smaller than $$$\frac{1}{1.4}$$$ if before that the sum was greater than $$$1$$$. This claim immediately finishes the case when we examine the case when we take $$$0$$$ elements from $$$B$$$. If we take $$$1$$$ elements from $$$B$$$ we just loop over all the possibilities. If we take $$$2$$$ elements from $$$B$$$, we can use $$$2$$$ pointers as you mentioned.

Did I understand correctly?

There are 2 observations:

1) The prime gaps are $$$O(b)$$$ on average

2) The difference between $$$\sqrt{n}$$$ and $$$\frac{p_1+p_2}{2} \cdot \frac{q_1+q_2}{2}$$$ is $$$O(b^2)$$$ on average.

So we can loop over the prime gaps divided by $$$2$$$(let's call then $$$a$$$ and $$$b$$$) and $$$\frac{p_1+p_2}{2} \cdot \frac{q_1+q_2}{2}$$$(let's call it $$$e$$$). Let's call $$$\frac{p_1+p_2}{2}$$$ $$$c$$$ and $$$\frac{q_1+q_2}{2}$$$ $$$d$$$. Then $$$n=(c^2-a^2)(d^2-b^2)=c^2d^2-a^2d^2-b^2c^2+a^2b^2=e^2+a^2b^2-a^2d^2-b^2c^2$$$, so we can easily get $$$a^2d^2+b^2c^2$$$.

$$$(a^2d^2+b^2c^2)^2=(a^2d^2-b^2c^2)^2+4abcd=(a^2d^2-b^2c^2)^2+4abe$$$ so we can easily get $$$a^2d^2-b^2c^2$$$ by square rooting and then finally get $$$a^2d^2$$$ and $$$b^2c^2$$$. Since we know $$$a$$$ and $$$b$$$ this allows us to easily get the values of $$$c$$$ and $$$d$$$, so now the factors are $$$c-a$$$, $$$c+a$$$, $$$d-b$$$ and $$$d+b$$$.