Anyway, a quantum-resistant algorithm is usually meant to be one that resists the exponential speedup given by Shor's algorithm and its variants. In other words, a quantum-resistant algorithm can't be based on the hardness of integer factorization, discrete logarithms on any abelian group, class groups, and so on (i.e. all instances of the Abelian hidden subgroup problem).
The leading candidates for such hard problems are decoding a random linear code (McEliece), shortest/closest vector finding in a lattice (NTRU, GGH, [R]LWE, ...), multivariate equation system solving (HFE and friends), and in the specific case of digital signatures one-way functions (Merkle Tree signatures).
[1] http://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Syste...
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