Method to calculating e in RSA
This is easy, just pick $e$ as prime larger than $\max(p,q)$. As $\phi(n) = (p-1)(q-1)$ it has only prime factors smaller than $q$ and $p$.

You can also do trial and error. If $e$ is prime, the GCD test is very fast. But it is technically not necessary to choose $e$ prime. Also note that key generation is not time critical.

However, often one starts with $e \in \{ 3,5,17,257,65537 \}$ which are special primes. Then one choose appropriate $p$ and $q$.
These exponents have computational benefits as they are of the form $2^k+1$. That makes computation of the $e^\text{th}$ power fast. Note that there are attacks for small exponents, especially $e=3$. They are all related to bad implementations, i.e. padding and so on. The RSA-scheme itself is not affected.