A naive way to factor an integer number N is based on checking the remainder of the division of N by some number p smaller than square root of N. If the remainder is 0, we conclude that p is a factor. This method is in fact very inefficient: with a computer that can test for 1010 different p's per second (this is faster than any computer ever built), the average time to find the factor of a 60-digit long number would exceed the age of the universe !
Rather than this naive division method, quantum computers rely on a slightly different technique to perform efficient factorisation. Indeed it is possible to show that factoring a number can be related to the problem of evaluating the period of a function. To explain how this method works, let us take a simple example and let us imagine we want to find the prime factors of N = 15. To do so we pick a random number a smaller than N, for instance a = 7, and define a function f(x) = 7x mod 15. This function raises 7 to the power of some integer x and takes the remainder of the division by 15. For instance, if x = 3, f(x) = 13 because 73 = 343 = 15 times 22 +13. Mathematics shows that f(x) is periodic and that its period r can be related to the factors of 15. In our example, we can check easily that f(x) evaluates to 1, 7, 4, 13, 1, 7, 4... for the values of x = 0, 1, 2, 3, 4, 5, 6.... and conclude that the period is r = 4. With this information, computing the factors of N only requires to evaluate the greatest common divisor of N and ar/2 +/- 1. In our example computing the greatest common divisor of 15 and 50 =7 4/2 + 1 (or 48=7 4/2 - 1) returns indeed the values 5 (or 3), the factors of 15.
Obviously classical computers cannot make much of this new method: finding the period of f(x) requires to evaluate the function f(x) many times. In fact mathematicians tell us that the average number of evaluation required to find the period is of the same order of the number of divisions needed with the naive method we outlined first. With a quantum computer, the situation is completely different: by setting a quantum register in a superposition of states representing 0, 1, 2, 3, 4... it is possible to compute in a single go the values f(0), f(1), f(2) ... . These values are encoded in superposed states of a quantum register, retrieving the period from them requires another step (known as a quantum fourier transform), that can also be performed very efficiently on a quantum computer.