Local problems with primes I