I've been working on a problem now, but I'm having a difficult time due to my lack of familiarity with sieve methods (this is not a hw problem or anything like that btw)
Let $P$ be the set of all prime numbers up to $p$, and suppose that a negative integer $N$ and a positive integer $M$ are both co-prime to all elements of $P$.
If $S=\{(N+1,M-1),(N+2,M-2),...,(N+(p^2-1),M-(p^2-1))\}$ (note that the pair $(N+x,M-x)$ is one element), is there a known sieve method for determining a lower bound on the size of $R$, where $R$ is the set of all elements of $S$ such that neither $N+x$ nor $M-x$ is divisible by any element of $P$?
Consider $N=1=-M$.
Then $R=a-b$ where $p_a$ is the largest prime number less than $p_b^2 -1$.
This is because all the totatives of the $b$th-primorial (all numbers not divisible by a prime less than or equal to $p_b$) upto $p_b^2$, are the prime numbers between $p_b$ and $p_b^2$. So if $p_a$ is the largest prime less than $p_b^2 -1$, then the size of $R$ is $a-b$
Next consider $N=X=-M$. Then the question amounts to "given a sequence of consecutive numbers of length $p_b^2 -1$, how many members must be totative of the $b$th primorial?" Well this question is currently unknown.
As for the case where $N \neq -M$, well the complexity increases again, and is probably unknown.