I need to adapt the Sieve of Eratosthenes for the usual integers to find all Gaussian primes with norm less than a specific limit. How to apply it to finding all Gaussian primes with norm less than 100? Thank you very much!


In the Sieve of Eratosthenes for rational integers, you select the positive ones and list those in increasing size. You do the same for the Gaussian integers: list them by increasing norm. But you need to select only one representative from each associate class, that is, modulo multiplication by units. In the rational integers, the units are $\pm 1$. In the Gaussian integers they are $\pm 1$ and $\pm i$. So to normalize the Gaussian integers, you may assume that $|a| \le |b|$ in $a+bi$ because you can always multiply by $i$ to make it so, and you may also assume that $a \ge 0$ because you can always multiply by $-1$ to make it so.


EDIT1: what's below is quite wrong, or, to be more positive about it, woefully incomplete. Please see EDIT2.

Represent the Gaussians with norm less than 100 as the lattice points on or in the circle of radius 10 centered at the origin (I take it the norm of $a+bi$ is $a^2+b^2$). Concentrate on the 45 degree sector between the real axis and the line $x=y$. Ignore the points $(0,0)$ and $(1,0)$. Take the closest point to the origin (which is $(1,1)$, corresponding to the number $1+i$), circle it (that's your first prime), and cross out everything else on the line connecting it to the origin. Among the points remaining, take the one closest to the origin, and iterate the procedure until termination.

EDIT2: Crossing out everything on the line through $(0,0)$ and $(a,b)$ will only cross out the multiples of $a+bi$ by ordinary integers, and that's not good enough - one must also cross out the multiples by other Gaussian integers. These form a $\it lattice$ generated by $a+bi$ and $b-ai$. Anyone unfamiliar with this concept is encouraged to plot (for example) the points ${\bf u}=(2,1)$ and ${\bf v}=(1,-2)$, think of them as vectors, then start plotting linear combinations of the two vectors with integer coefficients, $c{\bf u}+d{\bf v}$ with $c$ and $d$ integers. You'll see a simple pattern - that's a lattice, and you have to cross out all the points in it when you circle $(2,1)$.