Traditionally, the two questions in the title refer to the same problem: you test all possible factors (it is clearly enough to test all possible prime factors). If one of them divides your number evenly, that's your factor; if none of them works, the number is prime. (Today there are ways of getting high-confidence answers to the second question without touching the first: see Industrial-grade Primes).
If a number n is composite, it must have at least one prime
factor less than
. So it is enough to check if n
is divisible by any one of the primes less than . For
example, to see that 193 is prime, it is enough to check that it
is not divisible by 2, 3, 5, 7, 11, 13 since
is too big.
In general, the number of primes less than k is approximately
k / logk (this is the
Prime Number Theorem),
so the number of primes we need to check
to see if n is prime is approximately / log().
In practice, there are much better methods for finding a factor: see A Tale of Two Sieves by Carl Pomerance as well as What are the best factoring methods in use today (learn also about the RSA Factoring Challenge). But the following example, using primitive methods, gives an idea of how much harder it is, in general, to factor than to multiply.
For example, suppose we are using two 15-digit numbers, both close
to 
. The number
of operations to check whether one of them is prime is approximately
, so around
for the two of them. Their product is
close to 
; to run an exhaustive search for the
prime factors of that number would require approximately
,
or about two million times as many, operations.
Back to the first codes page.