Малко баламската си го дал алгоритъма, зафоде. Първо, простите числа по-малки от n са около n/log(n), а точните квадрати само sqr(n). Така че алгоритъма трябва да се подхване от другия край. После, освен че х (ако означим 3p+37=x^2) е четно, то не се дели на 3. Първата цифра на р е : 1 ако x(mod 10)=0 ; 9 ако x(mod 10)=2,8 ; 3 ако x(mod 10)=4,6. Обаче първата цифра на р ти я знаеш априори ако правилно си подбираш интервалите за хиксовете. И т.н. Начинът за проверяване дали р е просто е съвсем друга бира, но не считам за уместно да се наизустяват алгоритми, и квадратичният върши работа. Грубо казано, ако си поставиш за цел да преровиш всички такива числа от 1 то N ще имаш sqr(3N)/30 проверки за простота. Това ти дава най-много линейна сложност за алгоритъма (при квадратичен критерий) и то с доста добра константа. Ако разбира се N ти е дадено предварително и си пуснеш един Ерастотен до sqr(N)преди цялата процедура, получаваш още по-добър резултат. Като цяло мисля че задачката е уместна за интервю, особено като включи и оценка на кандидата за сложността на алгоритъма.