Is there an alternative to full factorization for testing the Polya conjecture?
You can use a sieve to significantly improve the running time. Decide on a number $N$, say $N = 2^{30}$. Initialize an array of length $N \times 2$ bits: one to keep track of the parity of the number of prime factors, and the second to mark which numbers have been visited. Now run an algorithm similar to the sieve of Eratosthenes. The running time equals the total number of prime factors of all numbers up to $N$, which is roughly $N\log\log N$.

With this information in hand, it is easy to check for violations of the conjecture.