защо обаче казваш че Първата цифра на р е : 1 ако x(mod 10)=0 ; 9 ако x(mod 10)=2,8 ; 3 ако x(mod 10)=4,6

Ами смятай де, защото ПОСЛЕДНАТА цифра на р е такава в тези случаи. Защо ти трябва това ли? Ами в интервала x \in (sqr(3*10^n+37),sqr(3*2*10^n+37)) ще проверяваш само ако x(mod10)=0 ,x \in (sqr(3*9*10^n+37),sqr(3*10*10^n+37)) ако x(mod10)=4, 6 и x \in (sqr(3*3*10^n+37),sqr(3*4*10^n+37)) ако x(mod10)=2, 8. Оттук нататък проверката за еднаквост на първа и последна цифра изобщо отпада, а броят на проверките е намален с 60%.