primality checking is much easier that factoring. it's somewhat unintuitive, but there are deterministic methods of primality testing that don't tell you the factors.