1) Public key cryptography relies on difficulty of factoring products of large primes.
2) Non-quantum computers can factor these numbers, it is just that the nature of the problem seems to require an expensive (non-polynomial to size of input) algorithm on classical computers. With quantum computers a polynomial time algorithm exists (Shor's algorithm).
Otherwise the famous theorem that any integer >= 1 can be factored uniquely (up to order of the factors) into prime numbers would not hold (it even holds for 1, since 1 is defined as the product of zero factors).
Prime number guesses cannot be fully determined as prime fast and easily...however WE CAN brute force guess big prime numbers easily..for example 1/4 to 15 RSA keys can be brute forced guessed..not full brute force break as you still have the session keys to brute force but you get the idea