--- Robin Garcia <

sopadeajo2001@...> wrote:

> Here is a Pari program to find all the primes of the form a^2-2

>

>

{u=3;m=4000;v=u+m;forstep(a=u,v,2,t=a^2-2;c=ceil(sqrt(t/2));for(n=c,a-2,s=2*n^2-t;if(issquare(s),next(2)));print(t))}

>

> u must always be odd for the program to work.

> Choose the range you want from u odd to u+m

>

> Can you say how the algoritm works?

> Can you prove that this algoritm always works?

This is not instantly obvious, but on re-arranging the terms it drops out quite

easily. Your test doesn't just work for primes of the form a^2-2, but any value

of the form 8N+7, of which the above is a subset.

It relies on 2*x^2-y*2 being the canonical 8N+7 quadratic form.

See Atkin/Bernstein's Prime Sieves (primegen) paper.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign

/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________

Do You Yahoo!?

Tired of spam? Yahoo! Mail has the best spam protection around

http://mail.yahoo.com