Why does RSA need p and q to be prime numbers?
However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms.


Not categorically. Factoring a large integer is trivial if it is only composed of small factors.

A fairly naive algorithm for factoring N is the following:

while N &gt; 1:
  for p in increasing_primes:
    while p divides N:
      N = N / p
      factors.add(p)


With this algorithm, $340$ $282$ $366$ $920$ $938$ $463$ $463$ $374$ $607$ $431$ $768$ $211$ $456$ can be factored in exactly $128$ iterations of the innermost while. (The number, of course, is $2^{128}$)

The more prime factors a composite number has, the smaller those factors have to be. For example, $919 \cdot 677 = 622$ $163$. With the naive algorithm, this takes $157 + 1 = 158$ iterations to factor. A number of roughly the same size comprised of three factors, $73 \cdot 89 \cdot 97 = 630$ $209$, only takes $25 + 2 = 27$ iterations to factor.

Similarly, a 1000-digit number composed of two roughly equally-sized factors will take about $10^{497}$ iterations to factor. A 1000-digit number composed of 100 roughly equally-sized factors will take about $434$ $294$ $481 + 99 \approx 10^{9}$ iterations. And a 1000-digit number composed of 1000 roughly equally-sized factors will take about $4 + 999 \approx 10^{3}$ iterations.

So, to make factoring as difficult as possible, you want the prime factors to be as large as possible, which means you want N to have the fewest factors possible. With $p$ and $q$ prime, $N$ has two factors. With $p$ and $q$ composite, $N$ has at least four factors, possibly more.

Note that this is far from a complete answer on why (we think) RSA is secure, but I hope it gives a more intuitive / example-based idea of why $p$ and $q$ should be primes.

Note also that $p$ and $q$ should be similar in magnitude. If one is much larger than the other, factorization becomes easier. For example, if $p = 43$, the naive algorithm would only take $14$ iterations.

(After reading the comments (thanks Taemyr and Daz C), I corrected some mistakes in the answer. The main point is unaffected.)