The thing is that the prime numbers have to go through all of the filters. Although the prime numbers are a minority among the numbers they are not a very small

The thing is that the prime numbers have to go through all of the filters. Although the prime numbers are a minority among the numbers they are not a very small minority. In fact, a random number N has about a probability of 1/log(N) to be prime. So that could reduce N^2 to maybe N^2/log(N) but not any further. So I suppose the complexity actually is somewhere between N^2 and N^2/log(N), but that is not much less than N^2. The trick of only checking primes smaller than sqrt(N) reduces the complexity to N^1.5, also maybe involving some division by log(N), but that is actually an improvement in the exponent.