Is this algorithm for generating primes any good? We know that composite integers can be expressed as a difference of squares. $$N=a^2-b^2=(a-b)\times(a+b)$$
So if we wanted to generate primes using a difference of squares, we could simply multiply one of the square above by a non-square $(2,3,\ldots)$. We get $$N=a^2-m\times b^2$$
There are two simple precautions to take.  


*

*Make sure that the two terms have opposite parity; and

*Make sure that the two terms do not share a common factor greater than $1$.
We provide a simple example to illustrate how the algorithm works.
$$N_{1}=13^2 - 2\times 1^2=167$$
$$N_{2}=13^2 - 2\times 3^2=151$$ etc... We don't always get a prime, like in $$N_{3}=13^2 - 2\times 5^2=119=7\times 17$$ but we often do. We can continue subtracting $$2\times b^2$$ until we get a negative number. Even the negative numbers can often  be prime. And we can multiply either square by the multiplier m and we can use any multiplier. It does not have to be $2$.
So the question is, how good is this simple way to generate primes? We obviously have to run a primality test to verify if the numbers generated are indeed primes.

Notice that for example a number $151$ you have used can be written also as:
$13^2-2 \cdot 3^2=151$
$13^2-18 \cdot 1^2=151$
Looking for prime number $41$ you could go checking $a^2$:
...
$10^2-5 \cdot 4^2=10$
$11^2-5 \cdot 4^2=41$
In my opinion if you continue subtracting $m \cdot b^2$ or even checking for conditions whether a number is prime or not, it might be a problem locating numbers between $(N, 2N)$, where $N$ is $1000$-digit long or more.
