Program to find megaPrime numbers between 2 given integers
I think John Coleman did a good job explaining speeding up the testing for mega-primality, but you're still using trial division to test for primality. The Miller-Rabin test is much faster, and can be made deterministic given the size of your range.

The algorithm starts by checking if \$n\$ is 1 or even. These cases are trivial, and should return 0 unless \$n = 2\$.

Next we take n-1 and remove the largest power of 2. Put another way we want to find s and d such that \$2^sd = n - 1\$ and d is odd. For example, if \$n = 49\$, \$n - 1 = 2^43\$, so \$s = 4\$ and \$d = 3\$.

Next we pick a random number for \$a\$ such that \$1 \lt a \lt n - 1\$. Now we make a loop on \$r\$ where \$r\$ goes from 0 to \$s - 1\$ inclusively. If for all values of r:

\$a^{2^rd} \% n \ne n - 1\$ and \$a^d\%n\ne1 % n != 1\$, then \$n\$ is composite. Otherwise, \$n\$ has a large probability of being prime. If you test every \$a\$ where \$a = {2, 3, 5, 7, 11, 13, 17, 19, 23}\$ and \$n\$ comes up as a likely prime for every time, it is prime.

If you are unfamiliar with this you may want to do \$a^b \% c\$ one step at a time, but computing \$a^b\$ may take a long time, and will quite likely result in an overflow error.

Use this trick:


\$a^b \%c =\$
If \$b = 0\$ then 1
If \$b\$ is odd then \$(a^{b-1} \% c ) b \% c\$
If \$b\$ is even then \$(a^{\frac{b}{2}} \% c)^2 \% c\$


This way, the number is constantly being reduced, and as long as recursion is used, the time will scale logarithmically with the size of \$b\$.