  We show that there exists some $\delta > 0$ such that, for any set of
integers $B$ with $B\cap[1,Y]\gg Y^{1-\delta}$ for all $Y \gg 1$, there are
infinitely many primes of the form $a^2+b^2$ with $b\in B$. We prove a
quasi-explicit formula for the number of primes of the form $a^2+b^2 \leq X$
with $b \in B$ for any $|B|=X^{1/2-\delta}$ with $\delta < 1/10$ and $B
\subseteq [\eta X^{1/2},(1-\eta)X^{1/2}] \cap \mathbb{Z}$, in terms of zeros of
Hecke $L$-functions on $\mathbb{Q}(i)$. We obtain the expected asymptotic
formula for the number of such primes provided that the set $B$ does not have a
large subset which consists of multiples of a fixed large integer. In
particular, we get an asymptotic formula if $B$ is a sparse subset of primes.
For an arbitrary $B$ we obtain a lower bound for the number of primes with a
weaker range for $\delta$, by bounding the contribution from potential
exceptional characters.
