>Does this mean that we have a sort of bloom filter-esque test for primality?

This catches most non-primes ;)

bool maybe_prime(x) { return x % 2 && x % 3 && x % 5 && x % 7; }