It is obvious by construction that any natural number can be expressed as some product of primes. Now, if the Fundamental Theorem of Arithmetic is false, then there is another set of primes with the same product. We can divide out any prime that appears in both sets, so that we end up with two sets of primes with equal products and no primes in common. Take the largest prime P (looking over both sets). We need to show that P does not divide into the product of primes in the other set. We do this by induction, building up the product in the other set. We note that P does not divide into the first factor in the other set because that is prime. Then if P does not divide the product so far, we show that it won't divide that product multiplied by the next factor. Consider the current product modulo P, call this R (modulo P means "the remainder on dividing by P"). Now R > 0 because P does not divide the product so far. Clearly P divides PR. Now find the smallest number k > 0 for which P divides kR. We know that k < P. Then find the largest multiple of k that is less than P, sk say. Then P divides skR. But P also divides PR, so P divides (P-sk)R. But P-sk < k (otherwise sk wasn't the largest multiple), so k wasn't the smallest. So there is no such k, including in particular the next element in our product. Continuing this argument until we have reached the last element in the product, we have shown that P does not divide the other product of primes, so the theorem is true.
